Scheduling with processing set restrictions: A survey

Scheduling problems with processing set restrictions have been studied extensively by computer scientists and operations researchers under different names. These include “scheduling typed task systems,” “multi-purpose machine scheduling,” “scheduling with eligibility constraints,” “scheduling with p...

Full description

Saved in:
Bibliographic Details
Published in:International journal of production economics 2008-12, Vol.116 (2), p.251-262
Main Authors: Leung, Joseph Y.-T., Li, Chung-Lun
Format: Article
Language:English
Subjects:
Approximation
Computational complexity
Parallel machines
Processing set restrictions
Production scheduling
Scheduling
Scheduling algorithms
Scheduling Parallel machines Processing set restrictions Computational complexity Worst-case analysis
Studies
Worst-case analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Scheduling problems with processing set restrictions have been studied extensively by computer scientists and operations researchers under different names. These include “scheduling typed task systems,” “multi-purpose machine scheduling,” “scheduling with eligibility constraints,” “scheduling with processing set restrictions,” and “semi-matchings for bipartite graphs.” In this paper we survey the state of the art of these problems. Our survey covers offline and online problems, as well as nonpreemptive and preemptive scheduling environments. Our emphasis is on polynomial-time algorithms, complexity issues, and approximation schemes. While our main focus is on the makespan objective, other performance criteria are also discussed.
ISSN:0925-5273
1873-7579
DOI:10.1016/j.ijpe.2008.09.003