The complexity of scheduling job families about a common due date

The complexity of scheduling job families about a common due date

0.00 Avg rating0 Votes
Article ID: iaor19982341
Country: Netherlands
Volume: 20
Issue: 2
Start Page Number: 65
End Page Number: 74
Publication Date: Feb 1997
Journal: Operations Research Letters
Authors:
Keywords: scheduling
Abstract:

Family scheduling problems are characterized by a setup time structure where setups are only required between jobs from different families. We consider the problem of scheduling job families on parallel machines to minimize weighted deviation about a common due date. Various special cases of this problem have been considered in the literature. This note summarizes known complexity results and introduces new complexity results. We show that the total earliness/tardiness problem is unary NP-hard when the number of machines and families is arbitrary, thus generalizing an earlier result and answering a longstanding open question in the literature.

Reviews

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