科研之友
微信
新浪微博
Facebook
分享链接
摘要
We consider bi-objective parallel-machine scheduling in green manufacturing to minimize the makespan and total processing cost. Each machine has a different constant processing cost per unit time. For the objective of minimizing the makespan, given a total cost budget, we provide an approximation algorithm with a worst-case ratio of root 33+1/4 approximate to 1.686, which improves the previous bound of 2. For the objective of minimizing the total processing cost, subject to all the jobs must be completed before a given common deadline, we provide an approximation algorithm with a worst-case ratio of 2+r/3, where r is the ratio of the maximum to the minimum processing cost per unit time on a machine.
