×

A sequential exchange approach for minimizing earliness-tardiness penalties of single-machine scheduling with a common due date. (English) Zbl 1102.90024

Summary: This study focuses on a class of single-machine scheduling problems with a common due date where the objective is to minimize the total earliness–tardiness penalty for the jobs. A sequential exchange approach utilizing a job exchange procedure and three previously established properties in common due date scheduling was developed and tested with a set of benchmark problems. The developed approach generates results better than not only those of the existing dedicated heuristics but also in many cases those of meta-heuristic approaches. And the developed approach performs consistently well in various job settings with respect to the number of jobs, processing time and earliness–tardiness penalties for the jobs.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, K. R.; Scudder, G. D., Sequencing with earliness and tardiness penalties: A review, Operations Research, 38, 1, 22-36 (1990) · Zbl 0699.90052
[2] Biskup, D.; Feldmann, M., Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates, Computers and Operations Research, 28, 8, 787-801 (2001) · Zbl 1003.90020
[3] Cheng, T. C.E.; Gupta, M. C., Survey of scheduling research involving due date determination decisions, European Journal of Operational and Research, 38, 2, 156-166 (1989) · Zbl 0658.90049
[4] Gordon, V.; Proth, J. M.; Chu, C., A survey of the state-of-art of common due date assignment and scheduling research, European Journal of Operational Research, 139, 1, 1-25 (2002) · Zbl 1009.90054
[5] Feldmann, M.; Biskup, D., Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches, Computers and Industrial Engineering, 44, 2, 307-323 (2003)
[6] James, R. J.W., Using tabu search to solve the common due date early/tardy machine scheduling problem, Computers and Operations Research, 24, 3, 199-208 (1997) · Zbl 0889.90090
[7] Hall, N. G.; Kubiak, W.; Sethi, S. P., Earliness-tardiness scheduling problem, II: Deviation of completion times about a restrictive common due date, Operations Research, 39, 5, 847-856 (1991) · Zbl 0762.90037
[8] Hall, N. G.; Posner, M. E., Earliness-tardiness scheduling problem, I: Weighted deviation of completion times about a common due date, Operations Research, 39, 5, 836-846 (1991) · Zbl 0749.90041
[9] Hino, C. M.; Ronconi, D. P.; Mendes, A. B., Minimizing earliness and tardiness penalties in a single-machine problem with a common due date, European Journal of Operational Research, 160, 1, 190-201 (2005) · Zbl 1067.90043
[10] Hoogeveen, J. A.; van, S. L., De Velde, Scheduling around a small common due date, European Journal and Operational Research, 55, 2, 237-242 (1991) · Zbl 0755.90044
[11] Kanet, J. J., Minimizing the average deviation of job completion times about a common due date, Naval Research Logistics Quarterly, 28, 4, 643-651 (1981) · Zbl 0548.90037
[12] Kahlbacher, H. G., Scheduling with monotonous earliness and tardiness penalties, European Journal of Operational Research, 64, 2, 258-277 (1993) · Zbl 0776.90036
[13] Lee, C. Y.; Danusaputro, S. L.; Lin, C. S., Minimizing weighted number of tardy jobs and weighted earliness-tardiness penalties about a common due date, Computers and Operations Research, 18, 4, 379-389 (1991) · Zbl 0717.90037
[14] Lee, C. Y.; Kim, S. J., Parallel genetic algorithms for the earliness-tardiness job scheduling problem with general penalty weights, Computers and Industrial Engineering, 28, 2, 231-243 (1995)
[15] Panwalkar, S. S.; Smith, M. L.; Seidmann, A., Common due date assignment to minimize total penalty for the one machine scheduling problem, Operations Research, 30, 2, 391-399 (1982) · Zbl 0481.90042
[16] Smith, W. E., Various optimizers for single-stage production, Naval Research Logistics Quarterly, 3, 59-66 (1956)
[17] Szwarc, W., Single-machine scheduling to minimize absolute deviation of completion times from a common due date, Naval Research Logistics, 36, 5, 663-673 (1989) · Zbl 0674.90049
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.