ON THE COMPLEXITY OF PREEMPTIVE OPENSHOP SCHEDULING PROBLEMS

Authors
SRISKANDARAJAH C WAGNEUR E
Citation
C. Sriskandarajah et E. Wagneur, ON THE COMPLEXITY OF PREEMPTIVE OPENSHOP SCHEDULING PROBLEMS, European journal of operational research, 77(3), 1994, pp. 404-414
Citations number
19
Categorie Soggetti
Management,"Operatione Research & Management Science
Journal title
European journal of operational research → ACNP
ISSN journal
03772217
Volume
77
Issue
3
Year of publication
1994
Pages
404 - 414
Database
ISI
SICI code
0377-2217(1994)77:3<404:OTCOPO>2.0.ZU;2-0
Abstract
We investigate the complexity status of the preemptive openshop schedu ling problem. After reviewing recent studies of the shop with various objective functions, we define the concept of preempting job w.r. to a schedule, and state some general results for the preemptive openshop environment. These results are then used to show by reduction from the 3-Partition, that the n job-2 machine mean flow time problem with rea dy times and job preemption is unary NP-hard.