 Scheduling parallel machines with inclusive processing set restrictions and job rejectionJinwen Ou, Xueling Zhong and Xiangtong Qi Naval Research Logistics (NRL), 2016, vol. 63, issue 8, 667-681 Abstract: In this article, we study a parallel machine scheduling problem with inclusive processing set restrictions and the option of job rejection. In the problem, each job is compatible to a subset of machines, and machines are linearly ordered such that a higher‐indexed machine can process all those jobs that a lower‐indexed machine can process (but not conversely). To achieve a tight production due date, some of the jobs might be rejected at certain penalty. We first study the problem of minimizing the makespan of all accepted jobs plus the total penalty cost of all rejected jobs, where we develop a ( 5 3 + ε ) ‐approximation algorithm with a time complexity of O ( n 2 / ε 2 ) . We then study two bicriteria variants of the problem. For the variant problem of minimizing the makespan subject to a given bound on the total rejection cost, we develop a ( 5 3 + ε ) ‐approximation algorithm with a time complexity of O ( n m ε 2 · log P ) . For the variant problem of maximizing the total rejection cost of the accepted jobs subject to a given bound on the makespan, we present a 0.5‐approximation algorithm with a time complexity of O ( n log n ) . © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 667–681, 2017 Date: 2016 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:63:y:2016:i:8:p:667-681 Access Statistics for this article More articles in Naval Research Logistics (NRL) from John Wiley & Sons |
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.