A graph-oriented approach for the minimization of the number of late jobs for the parallel machines scheduling problem

0.00 Avg rating—0 Votes

Article ID:	iaor20062058
Country:	Netherlands
Volume:	165
Issue:	3
Start Page Number:	649
End Page Number:	656
Publication Date:	Sep 2005
Journal:	European Journal of Operational Research
Authors:	Maculan Nelson, Bornstein Claudio Thoms, Alcoforado Luciane Ferreira
Keywords:	graphs, networks: scheduling

Abstract:

An O(n²) algorithm is presented for the n jobs m parallel machines problem with identical processing times. Due dates for each job are given and the objective is the minimization of the number of late jobs. Preemption is permitted. The problem can be formulated as a maximum flow network model. The optimality proof as well as other properties and a complete example are given.

Reviews

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