×
Gordon, Valery S.; Strusevich, Vitaly A.

Single machine scheduling and due date assignment with positionally dependent processing times. (English) Zbl 1163.90781

Eur. J. Oper. Res. 198, No. 1, 57-62 (2009).
Summary: We consider single machine scheduling and due date assignment problems in which the processing time of a job depends on its position in a processing sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and, possibly, the total earliness of the scheduled jobs. We present polynomial-time dynamic programming algorithms in the case of two popular due date assignment methods: CON and SLK. The considered problems are related to mathematical models of cooperation between the manufacturer and the customer in supply chain scheduling.

Cited in 25 Documents

MSC:

90C39 Dynamic programming

Keywords:

single machine scheduling; common due date assignment; SLK due date assignment; positionally dependent processing times
Cite Review PDF
Full Text: DOI

References:

[1] Agnetis, A.; Hall, N. G.; Pacciarelli, D., Supply chain scheduling: Sequence coordination, Discrete Applied Mathematics, 154, 2044-2063 (2006) · Zbl 1111.90037
[2] Biskup, D., Single-machine scheduling with learning considerations, European Journal of Operational Research, 115, 173-178 (1999) · Zbl 0946.90025
[3] Cheng, T. C.E.; Ding, Q.; Lin, B. M.T., A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152, 1-13 (2004) · Zbl 1030.90023
[4] De, P.; Ghosh, J. B.; Wells, C. E., Optimal delivery time quotation and order sequencing, Decision Science, 22, 379-390 (1991)
[5] Gordon, V. S.; Proth, J.-M.; Strusevich, V. A., Scheduling with due date assignment, (Leung, J. Y.-T., Handbook of Scheduling: Algorithms, Models and Performance Analysis (2004), CRC Press: CRC Press Boca Raton), 21-1-21-22
[6] Gordon, V.S., Potts, C.N., Strusevich, V.A., Whitehead, J.D., in press. Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation. Journal of Scheduling. doi:10.1007/s10951-008-0064-x; Gordon, V.S., Potts, C.N., Strusevich, V.A., Whitehead, J.D., in press. Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation. Journal of Scheduling. doi:10.1007/s10951-008-0064-x · Zbl 1168.90441
[7] Hall, N. G.; Potts, C. N., Supply chain scheduling: Batching and delivery, Operations Research, 51, 566-584 (2003) · Zbl 1165.90455
[8] Kahlbacher, H. G.; Cheng, T. C.E., Parallel machine scheduling to minimize costs for earliness and number of tardy jobs, Discrete Applied Mathematics, 47, 139-164 (1993) · Zbl 0816.90084
[9] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 0366.68041
[10] Kuo, W.-H.; Yang, D.-L., Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect, European Journal of Operational Research, 174, 1184-1190 (2006) · Zbl 1103.90341
[11] Mosheiov, G., Scheduling problems with a learning effect, European Journal of Operational Research, 132, 687-693 (2001) · Zbl 1017.90051
[12] Mosheiov, G., A note on scheduling deteriorating jobs, Mathematical and Computer Modelling, 41, 883-886 (2005) · Zbl 1082.90038
[13] Pinedo, M. L., Planning and Scheduling in Manufacturing and Services (2005), Springer: Springer Berlin · Zbl 1078.90028
[14] Shabtay, D.; Steiner, G., Optimal due date assignment and resource allocation to minimize the weighted number of tardy jobs on a single machine, Manufacturing and Service Operations Management, 9, 332-350 (2007)
[15] Wang, J.-B., Flow shop scheduling jobs with position-dependent processing times, Journal of Applied Mathematics and Computing, 18, 383-391 (2005) · Zbl 1077.90032
[16] Wang, J.-B.; Xia, Z.-Q., Flow shop scheduling with a learning effect, Journal of the Operational Research Society, 56, 1325-1330 (2005) · Zbl 1082.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.