𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Scheduling for parallel dedicated machines with a single server

✍ Scribed by Celia A. Glass; Yakov M. Shafransky; Vitaly A. Strusevich

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
443 KB
Volume
47
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

✦ Synopsis

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is NP -hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst-case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two-machine flow shop and the open shop problems with a single server are also shown to be NP -hard in the strong sense. However, we reduce the two-machine flow shop no-wait problem with a single server to the Gilmore-Gomory traveling salesman problem and solve it in polynomial time.

πŸ“œ SIMILAR VOLUMES

A min-sum 3/2-approximation algorithm fo
A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines
✍ FabiΓ‘n A. Chudak πŸ“‚ Article πŸ“… 1999 πŸ› Springer US 🌐 English βš– 70 KB

We consider the problem of minimizing the sum of weighted completion times of jobs scheduled on unrelated parallel machines. That is, there are n jobs and m machines; job j takes p GH units of time if processed on machine i and has a weight w H . If C H is the completion time of job j, the objective

Lower bounds and algorithms for flowtime
Lower bounds and algorithms for flowtime minimization on a single machine with set-up times
✍ Simon Dunstall; Andrew Wirth; Kenneth Baker πŸ“‚ Article πŸ“… 2000 πŸ› Springer US 🌐 English βš– 165 KB πŸ‘ 2 views

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

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

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