×

Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation. (English) Zbl 1168.90441

Summary: We consider various single machine scheduling problems in which the processing time of a job depends either on its position in a processing sequence or on its start time. We focus on problems of minimizing the makespan or the sum of (weighted) completion times of the jobs. In many situations we show that the objective function is priority-generating, and therefore the corresponding scheduling problem under series-parallel precedence constraints is polynomially solvable. In other situations we provide counter-examples that show that the objective function is not priority-generating.

MSC:

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

References:

[1] Alidaee, B., & Womer, N. K. (1999). Scheduling with time dependent processing times: review and extensions. Journal of the Operational Research Society, 50, 711–720. · Zbl 1054.90542
[2] Bachman, A., Janiak, A., & Kovalyov, M. Y. (2002). Minimizing the total weighted completion time of deteriorating jobs. Information Processing Letters, 81, 81–84. · Zbl 1032.68019 · doi:10.1016/S0020-0190(01)00196-X
[3] Biskup, D. (1999). Single-machine scheduling with learning considerations. European Journal of Operational Research, 115, 173–178. · Zbl 0946.90025 · doi:10.1016/S0377-2217(98)00246-X
[4] Biskup, D. (2008). A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188, 315–329. · Zbl 1129.90022 · doi:10.1016/j.ejor.2007.05.040
[5] Browne, S., & Yechiali, U. (1990). Scheduling deteriorating jobs on a single processor. Operations Research, 38, 495–498. · Zbl 0703.90051 · doi:10.1287/opre.38.3.495
[6] Burdyuk, V. Y., & Reva, V. N. (1980). A method for optimizing functions over permutations under constraints. Kibernetika (Kiev), 1, 99–103 (in Russian). · Zbl 0447.68085
[7] Cheng, T. C. E., Ding, Q., & Lin, B. M. T. (2004). A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research, 152, 1–13. · Zbl 1030.90023 · doi:10.1016/S0377-2217(02)00909-8
[8] Cheng, T. C. E., & Kovalyov, M. Y. (1994). Scheduling with learning effects on job processing times (Working paper no. 06/94). Faculty of Business and Information Systems, The Hong Kong Polytechnic University.
[9] Cheng, M.-B., & Sun, S.-L. (2006). The single-machine scheduling problems with deteriorating jobs and learning effect. Journal of Zhejiang University-Science A, 7, 597–601. · Zbl 1103.68398 · doi:10.1631/jzus.2006.A0597
[10] Crauwels, H. A. J., Potts, C. N., & Van Wassenhove, L. N. (1997). Local search heuristics for single machine scheduling with batch set-up times to minimize total weighted completion time. Annals of Operations Research, 70, 261–279. · Zbl 0890.90095 · doi:10.1023/A:1018978322417
[11] Crauwels, H. A. J., Hariri, A. M. A., Potts, C. N., & Van Wassenhove, L. N. (1998). Branch and bound algorithms for single-machine scheduling with batch set-up times to minimize total weighted completion time. Annals of Operations Research, 83, 59–76. · Zbl 0913.90164 · doi:10.1023/A:1018920416308
[12] Gawiejnowicz, S., & Pankovska, L. (1995). Scheduling jobs with varying processing times. Information Processing Letters, 54, 175–178. · Zbl 0875.68421 · doi:10.1016/0020-0190(95)00009-2
[13] Gordon, V. S., & Shafransky, Y. M. (1978). Optimal ordering with series-parallel precedence constraints. Doklady Akademii Nauk BSSR, 22, 244–247 (in Russian). · Zbl 0394.90047
[14] Gordon, V. S., Proth, J.-M., & Strusevich, V. A. (2005). Single machine scheduling and due date assignment under series-parallel precedence constraints. Central European Journal of Operations Research, 13, 15–35. · Zbl 1136.90350
[15] Ho, K. I.-J., Leung, J. Y.-T., & Wei, W.-D. (1993). Complexity of scheduling tasks with time dependent execution times. Information Processing Letters, 48, 315–320. · Zbl 0942.68508 · doi:10.1016/0020-0190(93)90175-9
[16] Janiak, A., & Kovalyov, M. Y. (2006). Scheduling in a contaminated area: a model and polynomial algorithms. European Journal of Operational Research, 173, 125–132. · Zbl 1125.90354 · doi:10.1016/j.ejor.2004.12.012
[17] Kuo, W.-H., & Yang, D.-L. (2006a). Minimizing the makespan in a single machine scheduling problem with a time-based learning effect. Information Processing Letters, 97, 64–67. · Zbl 1184.68131 · doi:10.1016/j.ipl.2005.09.007
[18] Kuo, W.-H., & Yang, D.-L. (2006b). 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. · Zbl 1103.90341 · doi:10.1016/j.ejor.2005.03.020
[19] Lawler, E. L. (1978). Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Annals of Discrete Mathematics, 2, 75–90. · Zbl 0374.68033 · doi:10.1016/S0167-5060(08)70323-6
[20] Lawler, E. L., & Sivazlian, B. D. (1978). Minimization of time-varying costs in single-machine sequencing. Operations Research, 26, 563–569. · Zbl 0385.90055 · doi:10.1287/opre.26.4.563
[21] Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1993). Sequencing and scheduling: algorithms and complexity. In S. C. Graves, A. H. G. Rinnooy, & P. H. Zipkin (Eds.), Handbooks in operations research and management science : Vol. 4. Logistics of production and inventory (pp. 445–522). Amsterdam: North-Holland.
[22] Möhring, R. H., & Rademacher, F. J. (1985). Generalized results on the polynomiality of certain weighted sum scheduling problems. Methods of Operations Research, 49, 405–417. · Zbl 0561.90049
[23] Monma, C. L., & Sidney, J. B. (1979). Sequencing with series-parallel precedence constraints. Mathematics of Operations Research, 4, 215–234. · Zbl 0448.90025 · doi:10.1287/moor.4.3.215
[24] Monma, C. L., & Sidney, J. B. (1987). Optimal sequencing via modular decomposition: characterization of sequencing functions. Mathematics of Operations Research, 12, 22–31. · Zbl 0622.90050 · doi:10.1287/moor.12.1.22
[25] Mosheiov, G. (1996). {\(\Lambda\)}-shaped policies to schedule deteriorating jobs. Journal of the Operational Research Society, 47, 1184–1191. · Zbl 0869.90039 · doi:10.1057/jors.1996.146
[26] Mosheiov, G. (2001). Scheduling problems with a learning effect. European Journal of Operational Research, 132, 687–693. · Zbl 1017.90051 · doi:10.1016/S0377-2217(00)00175-2
[27] Mosheiov, G. (2005). A note on scheduling deteriorating jobs. Mathematical and Computer Modelling, 41, 883–886. · Zbl 1082.90038 · doi:10.1016/j.mcm.2004.09.004
[28] Ng, C. T., Cheng, T. C. E., Bachman, A., & Janiak, A. (2002). Three scheduling problems with deteriorating jobs to minimize the total completion time. Information Processing Letters, 81, 327–333. · Zbl 1059.90063 · doi:10.1016/S0020-0190(01)00244-7
[29] Reva, V. N. (1979). On an algorithm for optimizing functions over the permutations of a partially ordered set. In Actual Problems of computers and programming (pp. 92–95). Dnepropetrovsk (in Russian).
[30] Rothkopf, M. E. (1966). Scheduling independent tasks on parallel processors. Management Science, 12, 437–447. · doi:10.1287/mnsc.12.5.437
[31] Shafransky, Y. M. (1978a). On optimal sequencing for deterministic systems with a tree-like partial order. Vestsi Akademii Navuk BSSR, Seria Fizika-Matematychnykh Navuk, 2, 120 (in Russian).
[32] Shafransky, Y. M. (1978b). Optimization for deterministic scheduling systems with a tree-like partial order. Vestsi Akademii Navuk BSSR, Seria Fizika-Matematychnykh Navuk, 2, 119 (in Russian).
[33] Shafransky, Y. M. (1980). On a problem of minimizing functions over a set of permutations of partially ordered elements, part I. Vestsi Akademii Navuk BSSR, Seria Fizika-Matematychnykh Navuk, 5, 132 (in Russian).
[34] Sidney, J. B., & Steiner, G. (1986). Optimal sequencing by modular decomposition: polynomial algorithms. Operations Research, 34, 606–612. · Zbl 0609.90068 · doi:10.1287/opre.34.4.606
[35] Smith, W. E. (1956). Various optimizers for single stage production. Naval Research Logistics Quarterly, 3, 59–66. · doi:10.1002/nav.3800030106
[36] Tanaev, V. S. (1965). Some objective functions of a single-stage production. Doklady Akademii Nauk BSSR, 9, 11–14 (in Russian).
[37] Tanaev, V. S., Gordon, V. S., & Shafransky, Y. M. (1984). Scheduling theory. Single-stage systems. Moscow: Nauka (in Russian); translated into English by Kluwer Academic, Dordrecht, 1994. · Zbl 0827.90079
[38] Valdes, J. R., Tarjan, E., & Lawler, E. L. (1982). The recognition of series-parallel digraphs. SIAM Journal on Computing, 11, 361–370. · Zbl 0478.68065 · doi:10.1137/0211023
[39] Wang, J.-B., Ng, C. T., & Cheng, T. C. E. (2008). Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint. Computers and Operations Research, 35, 2684–2693. · Zbl 1278.90261 · doi:10.1016/j.cor.2007.05.002
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.