Article ID: | iaor20043063 |
Country: | United Kingdom |
Volume: | 31 |
Issue: | 3 |
Start Page Number: | 317 |
End Page Number: | 345 |
Publication Date: | Mar 2004 |
Journal: | Computers and Operations Research |
Authors: | Werner Frank, Lauff Volker |
Keywords: | combinatorial analysis |
In this paper, the complexity and some other properties of several multi-stage problems with a non-regular performance measure are investigated. Mainly, we deal with two-machine problems. The problems are extensions of a one-machine problem with a common due date and a non-regular optimization criterion, where the sum of absolute deviations of the completion times from the due date is to be minimized. There are two reasonable generalizations. Either, the objective function is kept the same as in the one-machine problem, where the completion time is now the completion time of the last operation of the job, or a second penalty is added to this term which takes into account the storage costs of the intermediate. For both types of problems, we study the flow shop, the job shop, and the open shop environment. In the case of intermediate storage costs, we distinguish the cases of a due date