Scheduling parallel machines with inclusive processing set restrictions and job rejection

Scheduling parallel machines with inclusive processing set restrictions and job rejection

0.00 Avg rating0 Votes
Article ID: iaor2017129
Volume: 63
Issue: 8
Start Page Number: 667
End Page Number: 681
Publication Date: Dec 2016
Journal: Naval Research Logistics (NRL)
Authors: , ,
Keywords: manufacturing industries, scheduling, combinatorial optimization, simulation
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 ) .

Reviews

Required fields are marked *. Your email address will not be published.