Article ID: | iaor20031861 |
Country: | Netherlands |
Volume: | 142 |
Issue: | 3 |
Start Page Number: | 435 |
End Page Number: | 443 |
Publication Date: | Nov 2002 |
Journal: | European Journal of Operational Research |
Authors: | Blazewicz Jacek, Kobler Daniel |
Keywords: | graphs |
Precedence constraints are a part of a definition of any scheduling problem. After recalling, in precise graph-theoretical terms, the relations between task-on-arc and task-on-node representations, we show the equivalence of two distinct results for scheduling problems. Furthermore, again using these links between representations, we exhibit several new polynomial cases for various problems of scheduling preemptable tasks on unrelated parallel machines under arbitrary resource constraints.