Scheduling jobs of equal length: Complexity, facets and computational results

Scheduling jobs of equal length: Complexity, facets and computational results

0.00 Avg rating0 Votes
Article ID: iaor19971843
Country: Netherlands
Volume: 72
Issue: 3
Start Page Number: 207
End Page Number: 227
Publication Date: Mar 1996
Journal: Mathematical Programming (Series A)
Authors: ,
Keywords: programming: integer
Abstract:

The following problem was originally motivated by a question arising in the automated assembly of printed circuit boards. Given are n jobs, which have to be prefromed on a single machine within a fixed timespan [0,T], subidivded into T unit-length subperiods. The processing time (or length) of each job equals p,p∈ℝ. The processing cost of each job is an arbitrary function of its start-time. The problem is to schedule all jobs so as to minimize the sum of the processing costs. This problem is proved to be NP-hard, already for p=2 and 0-1 processing costs. On the othr hand, when T=np+c, with c constant, the problem can be solved in polynomial time. A partial polyhedral description of the set of feasible solutions is presented. In particular, two classes of facet-defining inequalities are described, for which the separation problem is polynomially solvable. Also, the authors exhibit a class of objective functions for which the inequalities in the LP-relaxation guarantee integral solutions. Finally, they present a simple cutting plane algorithm and report on its performance on randomly generated problem instances.

Reviews

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