On the complexity and some properties of multi-stage scheduling problems with earliness and tardiness penalties

On the complexity and some properties of multi-stage scheduling problems with earliness and tardiness penalties

0.00 Avg rating0 Votes
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: ,
Keywords: combinatorial analysis
Abstract:

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 d = 0 (which leads to a regular optimization criterion) and a non-restrictive due date. We obtain the following results. The two-machine flow shop problem with intermediate storage costs defined in this paper is NP-hard in the strong sense for d = 0 as well as for a non-restrictive due date. We prove the similar results for the two-machine open shop problem. In absence of intermediate storage costs, the open shop and the job shop problem are polynomially solvable for a non-restrictive due date.

Reviews

Required fields are marked *. Your email address will not be published.