Abstract
In this paper, we study the single-machine scheduling problems with learning effect and setup time considerations. The setup times are proportional to the length of the already-processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). The objective functions are to minimize the sum of the quadratic job completion times, the total waiting time, the total weighted completion time, the maximum lateness, the total absolute differences in waiting times, and the sum of earliness penalties subject to no tardy jobs, respectively. We show that the sum of the quadratic job completion times minimization problem, the total waiting time minimization problem, the total absolute differences in waiting times minimization problem, and the sum of earliness penalties minimization problem subject to no tardy jobs can be solved in polynomial time, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under some special cases.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Biskup D (1999) Single-machine scheduling with learning considerations. Eur J Oper Res 115:173–178
Cheng TCE, Wang G (2000) Single machine scheduling with learning effect considerations. Ann Oper Res 98:273–290
Mosheiov G (2001) Scheduling problems with a learning effect. Eur J Oper Res 132:687–693
Mosheiov G (2001) Parallel machine scheduling with a learning effect. J Oper Res Soc 52:1165–1169
Mosheiov G, Sidney JB (2003) Scheduling with general job-dependent learning curves. Eur J Oper Res 147:665–670
Wang J-B, Xia Z-Q (2005) Flow-shop scheduling with a learning effect. J Oper Res Soc 56:1325–1330
Wang J-B (2005) Flow shop scheduling jobs with position-dependent processing times. J Appl Math Comput 18:383–391
Kuo W-H, Yang D-L (2006) Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect. Eur J Oper Res 174:1184–1190
Eren T, Guner E (2007) Minimizing total tardiness in a scheduling problem with a learning effect. Appl Math Model 31:1351–1361
Wang J-B, Ng CT, Cheng TCE, Liu LL (2008) Single-machine scheduling with a time-dependent learning effect. Int J Prod Econ 111:802–811
Cheng TCE, Wu CC, Lee W-C (2008) Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects. Inf Sci 178(11):2476–2487
Eren T, Guner E (2009) A bicriteria parallel machine scheduling with a learning effect. Int J Adv Manuf Technol 40:1202–1205
Wang L-Y, Wang J-B, Wang D, Yin N, Huang X, Feng E-M (2009) Single-machine scheduling with a sum-of-processing-time based learning effect and deteriorating jobs. Int J Adv Manuf Technol. doi:10.1007/s00170-009-1950-x
Wang L-Y, Wang J-B, Gao W-J, Huang X, Feng E-M (2009) Two single-machine scheduling problems with the effects of deterioration and learning. Int J Adv Manuf Technol. doi:10.1007/s00170-009-2145-1
Biskup D (2008) A state-of-the-art review on scheduling with learning effects. Eur J Oper Res 188:315–329
Allahverdi A, Gupta JND, Aldowaisan T (1999) A review of scheduling research involving setup considerations. Omega 27:219–239
Allahverdi A, Ng CT, Cheng TCE, Kovalyov MY (2008) A survey of scheduling problems with setup times or costs. Eur J Oper Res 187:985–1032
Koulamas C, Kyparisis GJ (2008). Single-machine scheduling problems with past-sequence-dependent setup times. Eur J Oper Res 187:1045–1049
Kuo W-H, Yang D-L (2007) Single-machine scheduling with past-sequence-dependent setup and learning effects. Inf Process Lett 102:22–26
Wang J-B (2008) Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect. Comput Ind Eng 55:584–591
Wang J-B, Wang D, Wang L-Y, Lin L, Yin N, Wang W-W (2009) Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times. Comput Math Appl 57:9–16
Wang J-B, Jiang Y, Wang G (2009) Single machine scheduling with past-sequence-dependent setup times and effects of deterioration and learning. Int J Adv Manuf Technol 41:1221–1226
Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Annal Discrete Math 5:287–326
Hardy GH, Littlewood JE, Polya G (1967) Inequalities. Cambridge University Press, London
Townsend W (1978) The single machine problem with quadratic penalty function of completion times: a branch-and-bound solution. Manage Sci 24:530–534
Bagchi UB (1989) Simultaneous minimization of mean and variation of flow-time and waiting time in single machine systems. Oper Res 37:118–125
Chang S, Schneeberger H (1988) Single machine scheduling to minimize weighted earliness subject to no tardy jobs. Eur J Oper Res 34:221–230
Qi X, Tu F-S (1998) Scheduling a single machine to minimize earliness penalties subject to the SLK due-date determination method. Eur J Oper Res 105:502–508
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, XR., Wang, JB., Gao, WJ. et al. Scheduling with past-sequence-dependent setup times and learning effects on a single machine. Int J Adv Manuf Technol 48, 739–746 (2010). https://doi.org/10.1007/s00170-009-2308-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-009-2308-0