## Abstract

Given are n jobs, which have to be performed on a single machine within a fixed timespan {1,2,…T}. The processing time (or length) of each job equals p, p Є IN. 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 other 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, 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 |
---|---|

Title of host publication | Integer Programming and Combinatorial Optimization. IPCO 1995 |

Editors | E. Balas, J. Clausen |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 277-291 |

Number of pages | 15 |

ISBN (Electronic) | 978-3-540-49245-0 |

ISBN (Print) | 978-3-540-59408-6 |

DOIs | |

Publication status | Published - 1995 |

Externally published | Yes |

Event | 4th International Conference on Integer Programming and Combinatorial Optimizatio (IPCO 1995) - Copenhagen, Denmark Duration: 29 May 1995 → 31 May 1995 Conference number: 4 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 920 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 4th International Conference on Integer Programming and Combinatorial Optimizatio (IPCO 1995) |
---|---|

Abbreviated title | IPCO 1995 |

Country | Denmark |

City | Copenhagen |

Period | 29/05/95 → 31/05/95 |

## Keywords

- Computational complexity
- Polyhedral description
- Scheduling