 Approximation algorithms for scheduling parallel machines with an energy constraint in green manufacturingWeidong Li and Jinwen Ou European Journal of Operational Research, 2024, vol. 314, issue 3, 882-893 Abstract: Motivated by current green manufacturing standards, in this paper we study a parallel-machine scheduling model in which the energy cost incurred on each machine is machine-dependent and proportional to the load of the machine. The objective is to determine a production schedule with the minimum makespan subject to the energy constraint that the total energy cost does not exceed a given bound. We provide a technical lemma that enables us to design a very efficient approximation algorithm with a worst-case bound that can arbitrarily approach 43, improving on the existing performance ratio of 33+14≈1.686 in the literature. By introducing the concept of a monotonic schedule, we are able to develop the first polynomial time approximation scheme for this scheduling problem. The scheduling problem studied in this paper is an important special case of the generalized assignment problem (GAP). Our techniques and results bring new insights into research on the GAP. Keywords: Scheduling; Green manufacturing; Energy consumption; Algorithm design and analysis; Approximation scheme (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:314:y:2024:i:3:p:882-893 DOI: 10.1016/j.ejor.2023.11.008 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.