Approximation algorithms for bi-objective parallel-machine scheduling in green manufacturing

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.

Automated summary

This paper discusses the bi-objective parallel-machine scheduling problem in green manufacturing, aiming to minimize the makespan and total processing cost. For the objective of minimizing the makespan, within a given total cost budget, an approximation algorithm is proposed with a worst-case ratio of root 33+1/4, approximately equal to 1.686, which improves the previous bound of 2. For the objective of minimizing the total processing cost, subject to the constraint that all jobs must be completed before a given common deadline, an approximation algorithm is provided 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.