SCHEDULING JOBS OF EQUAL LENGTH - COMPLEXITY, FACETS AND COMPUTATIONAL RESULTS

The following problem was originally motivated by a question arising i n the automated assembly of printed circuit boards. Given are n jobs, which have to be performed on a single machine within a fixed timespan [0, T], subdivided into T unit-length subperiods. The processing time (or length) of each job equals p, p is an element of N. The processin g cost of each job is an arbitrary function of its start-time. The pro blem is to schedule all jobs so as to minimize the sum of the processi ng costs. This problem is proved to be NP-hard, already for p=2 and 0- 1 processing costs. On the other hand, when T=np+c, with c constant, t he problem can be solved in polynomial time. A partial polyhedral desc ription of the set of feasible solutions is presented. In particular, two classes of facet-defining inequalities are described, for which th e separation problem is polynomially solvable. Also, we exhibit a clas s of objective functions for which the inequalities in the LP-relaxati on guarantee integral solutions. Finally, we present a simple cutting plane algorithm and report on its performance on randomly generated pr oblem instances.