Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem

Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20062051
Country: Netherlands
Volume: 165
Issue: 2
Start Page Number: 444
End Page Number: 456
Publication Date: Sep 2005
Journal: European Journal of Operational Research
Authors: ,
Keywords: optimization
Abstract:

In this paper we study both the non-preemptive and preemptive versions of the popular unit-time open shop scheduling problem. For the set of feasible schedules which satisfy a predetermined order of job completion times, we construct the linear description of the convex hull of the vectors of the job completion times. Based on the properties of the resulting scheduling polydehdron we show that the problem of constructing an optimal schedule minimizing an arbitary non-decreasing separable cost function of job completion times is polynomially solvable.

Reviews

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