Necessary and sufficient optimality conditions for scheduling unit time jobs on identical parallel machines

Autor(en): Brucker, Peter
Shakhlevich, Natalia V. 
Stichwörter: Engineering; Engineering, Manufacturing; Operations Research & Management Science; Optimality conditions; OPTIMIZATION; Parallel machine scheduling; Unit processing times
Erscheinungsdatum: 2016
Herausgeber: SPRINGER
Volumen: 19
Ausgabe: 6
Startseite: 659
Seitenende: 685
In this paper we characterize optimal schedules for scheduling problems with parallel machines and unit processing times by providing necessary and sufficient conditions of optimality. We show that the optimality conditions for parallel machine scheduling are equivalent to detecting negative cycles in a specially defined graph. For a range of the objective functions, we give an insight into the underlying structure of the graph and specify the simplest types of cycles involved in the optimality conditions. Using our results we demonstrate that the optimality check can be performed by faster algorithms in comparison with existing approaches based on sufficient conditions.
11th Workshop on New Challenges in Scheduling Theory, Ctr CNRS Paul Langevin, Aussois, FRANCE, MAR 31-APR 04, 2014
ISSN: 10946136
DOI: 10.1007/s10951-016-0471-3

Show full item record

Google ScholarTM