๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Batch scheduling with deadlines on parallel machines: An NP-hard case

โœ Scribed by Mikhail Y. Kovalyov; Yakov M. Shafransky

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
529 KB
Volume
64
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

The problem of scheduling groups of jobs on unrelated parallel machines in batches subject to group deadlines was studied by Brucker et al. ( 1997) and Kovalyov and Shafransky ( 1994). A classification of computational complexities of special cases was provided only for the situation when all groups have equal deadlines. We prove that the problem is strongly NP-hard for the case of different deadlines, identical machines, unit processing times and unit set-up times, and equal numbers of jobs in each group. The problem where machine deadlines are given instead of job deadlines is proved to be strongly NP-complete. @ 1997 Elsevier Science B.V.

๐Ÿ“œ SIMILAR VOLUMES

Parallel machine batching and scheduling
Parallel machine batching and scheduling with deadlines
โœ T. C. Edwin Cheng; Mikhail Y. Kovalyov ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Springer US ๐ŸŒ English โš– 137 KB ๐Ÿ‘ 1 views

In this paper, we study the problem of scheduling n independent jobs non-preemptively on m unrelated parallel machines. Each job j has a processing time and a deadline, the time at which the job must be completed. On each machine, jobs may be grouped to form batches containing continuously scheduled

Batch scheduling and common due date ass
Batch scheduling and common due date assignment problem: An NP-hard case
โœ Mikhail Y. Kovalyov ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 199 KB

An important special case of the problem studied in arises when there are equal set-up times and equal job processing times. Computational complexity of this case was indicated to be open, however. I prove its NP-hardness.