Approximation algorithms for bi-objective parallel-machine scheduling in green manufacturing. (February 2023)

• Record Type: Journal Article
• Authors: Jiang, Yiwei; Tang, Xuelian; Li, Kai; Cheng, T.C.E.; Ji, Min
• Is Part Of: Computers & industrial engineering. Volume 176(2023)
• Publication Date: 2023-02
• Subjects: Green manufacturing -- Parallel-machine scheduling -- Approximation algorithm -- Worst-case ratio; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108949
• Languages: English
• ISSNs: 0360-8352

Abstract

Abstract: 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 33 + 1 4 ≈ 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. Highlights: We consider bi-objective parallel-machine scheduling in green manufacturing. The goal is to minimize the makespan and total processing cost. We propose an improved approximation algorithm for the first goal. An approximation algorithm with the bound ( 2 + r )/3 is given for the second goal.