Some single-machine scheduling problems with actual time and position dependent learning effects
Tóm tắt
In this paper we study some single-machine scheduling problems with learning effects where the actual processing time of a job serves as a function of the total actual processing times of the jobs already processed and of its scheduled position. We show by examples that the optimal schedules for the classical version of problems are not optimal under this actual time and position dependent learning effect model for the following objectives: makespan, sum of kth power of the completion times, total weighted completion times, maximum lateness and number of tardy jobs. But under certain conditions, we show that the shortest processing time (SPT) rule, the weighted shortest processing time (WSPT) rule, the earliest due date (EDD) rule and the modified Moore’s Algorithm can also construct an optimal schedule for the problem of minimizing these objective functions, respectively.
Tài liệu tham khảo
Alidaee B, Womer NK (1999) Scheduling with time dependent processing times: Review and extensions. Journal of the Operational Research Society 50:711–720
Badiru AB (1992) Computational survey of univariate and multivariate learning curve models. IEEE Transactions on Engineering Management 39:176–188
Biskup D (1999) Single-machine scheduling with learning considerations. European Journal of Operational Research 115:173–178
Biskup D (2008) A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research 188:315–329
Cheng TCE, Ding Q, Lin BMT (2004) A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research 152:1–13
Cheng TCE, Wang G (2000) Single machine scheduling with learning effect considerations. Annals of Operations Research 98:273–290
Cheng TCE, Wu CC, Lee WC (2008) Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects. Information Science 178:2476–2487
Koulamas C, Kyparisis GJ (2007) Single-machine and two-machine flowshop scheduling with general learning function. European Journal of Operational Research 178:402–407
Kuo WH, Yang DL (2006) 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
Kuo WH, Yang DL (2007) Single-machine scheduling problems with the time-dependent learning effect. Computers and Mathematics with Application 53:1733–1739
Lee WC, Wu CC, Sung HJ (2004) A bi-criterion single-machine scheduling problem with learning considerations. Acta Informatica 40:303–315
Lin BMT (2007) Complexity results for single-machine scheduling with positional learning effects. Journal of Operational Research Society 58:1099–1102
Moore JM (1968) An n job one machine sequencing algorithm for minimizing the number of late jobs. Management Science 15:102–109
Mosheiov G (2001) Scheduling problems with learning effect. European Journal of Operational Research 132:687–693
Smith WE (1956) Various optimizers for single state production. Naval Research Logistics Quarterly 3:59–66
Townsend W (1978) The single machine problem with quadratic penalty function of completion times: a branch-and-bound solution. Management Science 24:530–534
Wang X, Cheng TCE (2007) Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan. European Journal of Operational Research 178:57–70
Wang JB (2007) Single-machine scheduling problems with the effects of learning and deterioration. Omega 35:397–402
Wang JB (2008) Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect. Computers and Industrial Engineering 55:584–591
Wang JB, Ng CT, Cheng TCE, Lin LL (2008) Single-machine scheduling with a time-dependent learning effect. International Journal of Production Economics 111:802–811
Wu CC, Lee WC (2008) Single machine scheduling problems with a learning effect. Applied Mathematical Modelling 32:1191–1197
Yelle LE (1979) The learning curve: Historical review and comprehensive survey. Decision Sciences 10:302–328