On decomposition of the total tardiness problem. (English) Zbl 0858.90072
Summary: As an improvement of the famous Lawler decomposition theorem for the one-machine total tardiness problem, some conditions on decomposition positions are obtained by Potts and Wassenhove, and are used by them to make the decomposition algorithm more efficient. In this paper, more conditions on the leftmost decomposition position are proved. Additional computational tests are described.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Baker, K. R., An introduction to sequencing and scheduling (1974), Wiley: Wiley New York |
| [2] | Du, J.; Leung, J. Y.-T., Minimizing total tardiness on one machine is NP-hard, Math. Oper. Res., 15, 3, 483-495 (1990) · Zbl 0714.90052 |
| [3] | Emmons, H., One-machine sequencing to minimize certain functions of job tardiness, Oper. Res., 17, 701-715 (1969) · Zbl 0176.50005 |
| [4] | Lawler, E. L., A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness, Ann. Discrete Math., 1, 331-342 (1977) · Zbl 0353.68071 |
| [5] | Potts, C. N.; Van Wassenhove, L. N., A decomposition algorithm for the single machine total tardiness problem, Oper. Res. Lett., 1, 177-182 (1982) · Zbl 0508.90045 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
