Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs. (English) Zbl 0916.90147
Summary: We consider a single machine scheduling problem involving both the scheduling of job processing and the scheduling of job delivery. A common due date for all the jobs and a delivery date for each job need to be determined in order to minimize the sum of earliness penalties, tardiness penalties, due date penalty, and delivery costs. Finished jobs are delivered in batches. There is no capacity limitation on a batch delivery and the cost per batch delivery is fixed and independent of the number of jobs in the batch. All the jobs completed before or at the due date are delivered in one batch at the due date. We present in this paper a polynomial dynamic programming algorithm for solving this problem.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Baker, K. R.; Scudder, G. D., Sequencing with earliness and tardiness penalties: A review, Operations Research, 38, 22-36 (1990) · Zbl 0699.90052 |
| [2] | Bector, C. Y.; Gupta, Y.; Gupta, M., Determination of an optimal common due date and optimal sequence in a single machine job shop, International Journal of Production Research, 26, 613-628 (1988) · Zbl 0644.90047 |
| [3] | Cheng, T. C.E., An algorithm for the CON due date determination and sequencing problem, Computers & Operations Research, 14, 537-542 (1987) · Zbl 0634.90030 |
| [4] | Cheng, T. C.E.; Chen, Z.-L., Parallel-machine scheduling with earliness and tardiness penalties, Journal of the Operational Research Society, 45, 685-695 (1994) · Zbl 0829.90077 |
| [5] | Cheng, T. C.E.; Gupta, M. C., Survey of scheduling research involving due date determination decisions, European Journal of Operational Research, 38, 156-166 (1989) · Zbl 0658.90049 |
| [6] | Cheng, T. C.E.; Kahlbacher, H. G., Scheduling with delivery and earliness penalties, Asia-Pacific Journal of Operational Research, 10, 145-152 (1993) · Zbl 0789.90041 |
| [7] | Hall, N. G.; Kubiak, W.; Sethi, S. P., Earliness-tardiness scheduling problems, II: Deviation of completion times about a restrictive common due date, Operations Research, 39, 847-856 (1991) · Zbl 0762.90037 |
| [8] | Hall, N. G.; Posner, M. E., Earliness-tardiness scheduling problems, I: Weighted deviation of completion times about a common due date, Operations Research, 39/5, 836-846 (1991) · Zbl 0749.90041 |
| [9] | Herrmann, J. W.; Lee, C.-Y., On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date, European Journal of Operational Research, 70, 272-288 (1993) · Zbl 0842.90060 |
| [10] | Lee, C.-Y.; Dunasaputro, S. L.; Lin, C. S., Minimizing weighted number of tardy jobs and weighted earliness-tardiness penalties about a common due date, Computers & Operations Research, 18, 379-389 (1991) · Zbl 0717.90037 |
| [11] | Li, C.-L.; Chen, Z.-L.; Cheng, T. C.E., A note on one-processor scheduling with asymmetric earliness and tardiness penalties, Operations Research Letters, 13, 45-48 (1993) · Zbl 0773.90037 |
| [12] | Li, C.-L.; Cheng, T. C.E., The parallel machine min-max weighted absolute lateness scheduling problem, Naval Research Logistics, 41, 33-46 (1994) · Zbl 0808.90082 |
| [13] | Li, C.-L.; Cheng, T. C.E.; Chen, Z.-L., Single-machine scheduling to minimize the weighted number of early and tardy agreeable jobs, Computers & Operations Research, 22, 205-219 (1995) · Zbl 0812.90068 |
| [14] | Panwalkar, S.; Smith, M.; Seidmann, A., Common due date assignment to minimize total penalty for one machine scheduling problem, Operations Research, 30, 391-399 (1982) · Zbl 0481.90042 |
| [15] | Sung, C. S.; Joo, U. G., A single-machine scheduling problem with earliness/tardiness and starting time penalties under a common due date, Computers & Operations Research, 19, 757-766 (1992) · Zbl 0767.90041 |
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.
