### Abstract

We consider the problem of minimizing the weighted sum of job completion times on a single machine (subject to certain job weights) with an additional side constraint on the weighted sum of job completion times (with respect to different job weights). This problem is NP-hard, and we provide a polynomial time approximation scheme for this problem. Our method is based on Lagrangian relaxation mixed with carefully guessing the positions of certain jobs in the schedule.

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

Title of host publication | Integer Programming and Combinatorial Optimization |

Subtitle of host publication | 10th International IPCO Conference, New York, NY, USA, June 7-11, 2004. Proceedings |

Editors | Daniel Bienstock, Georg Nemhauser |

Place of Publication | Heidelberg |

Publisher | Springer |

Pages | 298-307 |

ISBN (Electronic) | 978-3-540-25960-2 |

ISBN (Print) | 978-3-540-22113-5 |

DOIs | |

Publication status | Published - 2004 |

Event | 10th Conference on Integer Programming and Combinatorial Optimization, IPCO 2004 - New York, United States Duration: 7 Jun 2004 → 11 Jun 2004 Conference number: 10 |

### Publication series

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

Publisher | Springer |

Volume | 3064 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 10th Conference on Integer Programming and Combinatorial Optimization, IPCO 2004 |
---|---|

Abbreviated title | IPCO |

Country | United States |

City | New York |

Period | 7/06/04 → 11/06/04 |

### Keywords

- Scheduling
- Bicriteria optimization
- Approximation scheme

## Fingerprint Dive into the research topics of 'The Constrained Minimum Weighted Sum of Job Completion Times Problem'. Together they form a unique fingerprint.

## Cite this

Levin, A., & Woeginger, G. J. (2004). The Constrained Minimum Weighted Sum of Job Completion Times Problem. In D. Bienstock, & G. Nemhauser (Eds.),

*Integer Programming and Combinatorial Optimization: 10th International IPCO Conference, New York, NY, USA, June 7-11, 2004. Proceedings*(pp. 298-307). (Lecture Notes in Computer Science; Vol. 3064). Heidelberg: Springer. https://doi.org/10.1007/978-3-540-25960-2_23