On the complexity of generalized due date scheduling problems (Q1175769)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the complexity of generalized due date scheduling problems |
scientific article; zbMATH DE number 14476
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the complexity of generalized due date scheduling problems |
scientific article; zbMATH DE number 14476 |
Statements
On the complexity of generalized due date scheduling problems (English)
0 references
25 June 1992
0 references
A generalized due date scheduling problem is a problem for which due dates are not associated with the individual jobs, but are specified according to the position in which a job is completed. The authors define the generalized due date counterpart of most of the well-known single and multiple machine scheduling problems. The complexity of several of these problems is determined. Surprisingly some of the NP-hard problems become polynomially solvable in the case of generalized due dates. The paper contains a list of the complexity results and also a list of problems with open complexity status.
0 references
generalized due date scheduling
0 references
0 references
0 references
0.9277047
0 references
0.9016753
0 references
0.8985512
0 references
0.8967554
0 references
0.8878124
0 references
