# 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:10.1023/A:1018997431986)

## 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 |