## Abstract

The following problem was originally motivated by a question arising in the automated assembly of printed circuit boards. Given aren jobs, which have to be performed on a single machine within a fixed timespan [0,T], subdivided intoT unit-length subperiods. The processing time (or length) of each job equalsp,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 forp=2 and 0–1 processing costs. On the other hand, whenT=np+c, withc 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, we exhibit a class of objective functions for which the inequalities in the LP-relaxation guarantee integral solutions.

Finally, we present a simple cutting plane algorithm and report on its performance on randomly generated problem instances.

This problem is proved to be NP-hard, already forp=2 and 0–1 processing costs. On the other hand, whenT=np+c, withc 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, we exhibit a class of objective functions for which the inequalities in the LP-relaxation guarantee integral solutions.

Finally, we present a simple cutting plane algorithm and report on its performance on randomly generated problem instances.

Original language | English |
---|---|

Pages (from-to) | 207-227 |

Journal | Mathematical Programming |

Volume | 72 |

Issue number | 3 |

DOIs | |

Publication status | Published - 31 Mar 1996 |

Externally published | Yes |

## Keywords

- scheduling
- computational complexity
- polyhedral description