Open shop scheduling with some additional constraints |
| |
Authors: | D de Werra J Erschler |
| |
Institution: | (1) Département de Mathématiques, Swiss Federal Institute of Technology in Lausanne, Switzerland;(2) Laboratoire d'Automatique et d'Analyse de Systèmes, C.N.R.S., Toulouse, France |
| |
Abstract: | An open shop scheduling problem is presented; preemptions during processing of a job on a processorp is allowed but the job cannot be sent on another processorq before it is finished onp. A graph-theoretical model is described and a characterization is given for problems where schedules with such restricted preemptions useT time units whereT is the maximum of the processing times of the jobs and of the working times of the processors. The general case is shown to be NP-complete. We also consider the case where some constraints of simultaneity are present. Complexity of the problem is discussed and a solvable case is described. |
| |
Keywords: | Open shop scheduling preemptions line-perfectness unrelated processors chromatic scheduling simultaneity |
本文献已被 SpringerLink 等数据库收录! |