✦ LIBER ✦

Lower bounds and algorithms for flowtime minimization on a single machine with set-up times

✍ Scribed by Simon Dunstall; Andrew Wirth; Kenneth Baker

Publisher: Springer US
Year: 2000
Tongue: English
Weight: 165 KB
Volume: 3
Category: Article
ISSN: 1094-6136
DOI: 10.1002/(sici)1099-1425(200001/02)3:1<51::aid-jos34>3.0.co;2-k

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the scheduling of N jobs divided into G families for processing on a single machine. No set-up is necessary between jobs belonging to the same family. A set-up must be scheduled when switching from the processing of family i jobs to those of another family j, i = j, the duration of this set-up being the sequence-independent set-up time s j for family j. We propose lower bounds for the problem of minimizing the weighted owtime on a single machine with family set-up times and static job availability. These lower bounds are incorporated into a branch-and-bound algorithm which can e ciently solve instances with up to 70 jobs.

📜 SIMILAR VOLUMES

Polynomial time algorithms for minimizin

Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times

✍ Philippe Baptiste 📂 Article 📅 1999 🏛 Springer US 🌐 English ⚖ 102 KB 👁 2 views

We study the problem of minimizing the weighted number of late jobs to be scheduled on a single machine when processing times are equal. In this paper, we show that this problem, as well as its preemptive variant, are strongly polynomial. When preemption is not allowed ( 1"p H "p, r H " w H ; H ), t

A polynomial-time approximation scheme f

A polynomial-time approximation scheme for single-machine sequencing with delivery times and sequence-independent batch set-up times

✍ Gerhard J. Woeginger 📂 Article 📅 1998 🏛 Springer US 🌐 English ⚖ 100 KB 👁 2 views

We investigate the single-machine sequencing problem in which each job has a processing time and a delivery time. The jobs are divided into families and a set-up time is incurred whenever there is a switch from a job in one family to a job in another family. This set-up only depends on the family of