Shop scheduling problems under precedence constraints
Strusevich, V.A. (1997) Shop scheduling problems under precedence constraints. Annals of Operations Research, 69. pp. 351-377. ISSN 0254-5330 (Print), 1572-9338 (Online) (doi:https://doi.org/10.1023/A:1018997431986)
Full text not available from this repository.Abstract
The paper considers a scheduling model that generalizes the well-known open shop, flow shop, and job shop models. For that model, called the super shop, we study the complexity of finding a time-optimal schedule in both preemptive and non-preemptive cases assuming that precedence constraints are imposed over the set of jobs. Two types of precedence rela-tions are considered. Most of the arising problems are proved to be NP-hard, while for some of them polynomial-time algorithms are presented.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | shop scheduling, precedence constraints, computational complexity |
Subjects: | Q Science > QA Mathematics |
Pre-2014 Departments: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group |
Related URLs: | |
Last Modified: | 14 Oct 2016 08:59 |
URI: | http://gala.gre.ac.uk/id/eprint/41 |
Actions (login required)
View Item |