| Article ID: | iaor2000175 |
| Volume: | 27 |
| Issue: | 83 |
| Start Page Number: | 35 |
| End Page Number: | 49 |
| Publication Date: | Jan 1997 |
| Journal: | Ricerca Operativa |
| Authors: | Dror Moshe, Kubiak Wieslaw, Dell'Olmo Paolo |
In this paper we introduce a distinction between the weak and strong modes of scheduling jobs with linear precedence order (chains) in machine scheduling. We study complexity implications of the two modes for a variety of machine scheduling problems. In most cases, NP-completeness for the weak chain implies NP-completeness for the strong chain. However, this is not true in general, i.e. the ‘strong’–‘weak’ distinction is proper.