Some new efficient methods to solve the \(n/1/r_ i/\sum{}T_ i\) scheduling problem. (English) Zbl 0760.90055

Summary: We prove a sufficient condition for local optimality to solve the \(n/1/r_ i/\sum T_ i\) scheduling problem which is known to be NP-hard. We then define a new dominant subset of schedules on the basis of this condition and propose several new approximate algorithms to construct schedules belonging to this subset. Numerical experiments enable us to compare them with classical approximate algorithms.


90B35 Deterministic scheduling theory in operations research
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI


[1] Baker, K. R., Introduction to Sequencing and Scheduling (1974), John Wiley: John Wiley New York
[2] Baker, K. R.; Bertrand, J. W.M., A dynamic priority rule for scheduling against due-dates, Journal of Operations Management, 3, 1, 37-42 (1982)
[3] Chu, C.; Portmann, M. C., Minimisation de la somme des retards pour les problèmes d’ordonnancement à une machine, (Rapport de recherche No. 1023 (1989), l’INRIA: l’INRIA Rocquencourt, France), avril
[4] Chu, C.; Portmann, M. C., Single machine scheduling problems with release dates, EURO WG-PMS (June 20-22, 1990), Compiègne
[5] Conway, R. W.; Maxwell, W. L.; Miller, L. W., Theory of Scheduling (1967), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 1058.90500
[6] Du, J.; Leung, J. Y.-T., Minimizing total tardiness on one machine is NP-hard, Mathematics of Operations Research, 15, 483-495 (1990) · Zbl 0714.90052
[7] Emmons, H., One-machine sequencing to minimize certain functions of job tardiness, Operations Research, 17, 701-715 (1969) · Zbl 0176.50005
[8] Fisher, M. L., A dual algorithm for the one-machine scheduling problem, Mathematical Programming, 11, 229-251 (1976) · Zbl 0359.90039
[9] Lawler, E. L., A ‘pseudopolynomial’ algorithm for sequencing jobs to minimize total tardiness, Annals of Discrete Mathematics, 1, 331-342 (1977) · Zbl 0353.68071
[10] Lawler, E. L., A fully polynomial approximation scheme for the total tardiness problem, Operations Research Letters, 1, 207-208 (1982) · Zbl 0511.90074
[11] Panwalker, S. S.; Iskander, W., A survey of scheduling rules, Operations Research, 25/1, 45-60 (1977) · Zbl 0369.90054
[12] Potts, C. N.; Van Wassenhove, L. N., A decomposition algorithm for the single machine total tardiness problem, Operation Research Letters, 1/5, 177-181 (1982) · Zbl 0508.90045
[13] Potts, C. N.; Van Wassenhove, L. N., Dynamic programming and decomposition approaches for the single machine total tardiness problem, European Journal of Operational Research, 32, 405-414 (1987) · Zbl 0627.90055
[14] Rinnooy Kan, A. H.G., Machine Sequencing Problems: Classification, Complexity and Computation (1976), Nijhoff: Nijhoff The Hague · Zbl 0366.90092
[15] Sen, T. T.; Austin, L. M.; Ghandforoush, P., An algorithm for the single-machine sequencing problem to minimize total tardiness, IEE Transactions, 15/4, 363-366 (1983)
[16] Smith, W. E., Various optimizers for single-stage production, Naval Research Logistics Quarterly, 3, 59-66 (1956)
[17] Srinivasan, V., A hybrid algorithm for the one-machine sequencing problem to minimize total tardiness, Naval Research Logistics Quarterly, 18/3, 317-327 (1971) · Zbl 0229.90029
[18] Vepsalainen, A. P.J.; Morton, T. E., Priority rules for job shops with weighted tardiness costs, Management Science, 33/8, 1035-1047 (1987)
[19] Wilkerson, L. J.; Irwin, J. D., An improved algorithm for scheduling independent tasks, AIIE Transactions, 3, 239-245 (1971)
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.