No Access

An Optimal Online Algorithm for Scheduling with Learning Consideration

School of Management Engineering, Qingdao University of Technology, Qingdao 266525, P. R. China

University Research Center for Smart City, Construction and Management of Shandong, Province, Qingdao 266525, P. R. China

E-mail Address: sungirlmr@163.com

Corresponding author.

Search for more papers by this author

Wenwen Han

School of Management Engineering, Qingdao University of Technology, Qingdao 266525, P. R. China

University Research Center for Smart City, Construction and Management of Shandong, Province, Qingdao 266525, P. R. China

E-mail Address: eosenh@163.com

Search for more papers by this author

Cuixia Miao

School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China

E-mail Address: miaocuixia@126.com

Search for more papers by this author

, and

Juan Zou

School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China

E-mail Address: zoujuanjn@163.com

Search for more papers by this author

https://doi.org/10.1142/S0217595921400029Cited by:1 (Source: Crossref)

This article is part of the issue:

Special Issue on Frontiers of Operations Research of YFORSC 2020

Abstract

This paper investigates a classic online scheduling problem with learning effect on a single machine. Specifically, a number of independent jobs that arrive online over time will be processed on a single machine and learning effect implies that the real processing time of job $J_{j}$ $J_{j}$ is a non-increasing function of its position $h$ $h$ , i.e., $p_{j h} = p_{j} α^{h - 1}$ $p_{j h} = p_{j} α^{h - 1}$ , where $p_{j}$ $p_{j}$ is the basic processing time of job $J_{j}$ $J_{j}$ and $0 < α < 1$ $0 < α < 1$ is the learning index. Our goal is to minimize the total completion time of all jobs. For the problem, we develop a deterministic polynomial time online algorithm called Delayed Shortest Basic Processing Time (DSBPT) and state that it is an online algorithm with a competitive ratio of 2, which matches the lower bound of the online scheduling problem we focus on.

Keywords:

References

Biskup, D (1999). Single-machine scheduling with learning considerations. European Journal of Operational Research, 115(1), 173–178. Crossref, Web of Science, Google Scholar
Biskup, D (2008). A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188(2), 315–329. Crossref, Web of Science, Google Scholar
Cheng, TCE, WH Kuo and DL Yang (2014). Scheduling with a position-weighted learning effect. Optimization Letters, 8(1), 293–306. Crossref, Web of Science, Google Scholar
Cheng, TCE, CC Wu, JC Chen, WH Wu and SR Cheng (2013). Two-machine flowshop scheduling with a truncated learning function to minimize the makespan. International Journal of Production Economics, 141(1), 79–86. Crossref, Web of Science, Google Scholar
Cheng, TE, CC Wu and WC Lee (2008). Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects. Information Sciences, 178(11), 2476–2487. Crossref, Web of Science, Google Scholar
Cheng, M, S Xiao and G Liu (2018). Single-machine rescheduling problems with learning effect under disruptions. Journal of Industrial and Management Optimization, 14(3), 967–980. Crossref, Web of Science, Google Scholar
Fan, W, J Pei, X Liu, PM Pardalos and M Kong (2018). Serial-batching group scheduling with release times and the combined effects of deterioration and truncated job-dependent learning. Journal of Global Optimization, 71(1), 147–163. Crossref, Web of Science, Google Scholar
Gordon, VS, CN Potts, VA Strusevich and JD Whitehead (2008). Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation. Journal of Scheduling, 11(5), 357–370. Crossref, Web of Science, Google Scholar
Hoogeveen, JA and AP Vestjens (1996). Optimal on-line algorithms for single-machine scheduling. Integer Programming and Combinatorial Optimization, 1084, 404–414. Crossref, Google Scholar
Janiak, A and R Rudek (2008). A new approach to the learning effect: Beyond the learning curve restrictions. Computers & Operations Research, 35(11), 3727–3736. Crossref, Web of Science, Google Scholar
Li, XJ, JJ Wang and XR Wang (2015). Single-machine scheduling with learning effect, deteriorating jobs and convex resource dependent processing times. Asia-Pacific Journal of Operational Research, 32(5), 1–13. Link, Web of Science, Google Scholar
Ma, R, JP Tao and JJ Yuan (2016). Online scheduling with linear deteriorating jobs to minimize the total weighted completion time. Applied Mathematics and Computation, 273, 570–583. Crossref, Web of Science, Google Scholar
Ma, R and JJ Yuan (2017). Online scheduling to minimize the total weighted completion time plus the rejection cost. Journal of Combinatorial Optimization, 34(2), 483–503. Crossref, Web of Science, Google Scholar
Ma, R and SN Guo (2021). Applying “Peeling Onion” approach for competitive analysis in online scheduling with rejection. European Journal of Operational Research, 290(2021), 57–67. Crossref, Web of Science, Google Scholar
Mosheiov, G and JB Sidney (2003). Scheduling with general job-dependent learning curves. European Journal of Operational Research, 147(3), 665–670. Crossref, Web of Science, Google Scholar
Rustogi, K and VA Strusevich (2012). Simple matching versus linear assignment in scheduling models with positional effects: A critical review. European Journal of Operational Research, 222(3), 393–407. Crossref, Web of Science, Google Scholar
Wang, JB and TE Cheng (2007). Scheduling problems with the effects of deterioration and learning. Asia-Pacific Journal of Operational Research, 24(2), 245–261. Link, Web of Science, Google Scholar
Wang, JB, F Liu and JJ Wang (2019). Research on m-machine flow shop scheduling with truncated learning effects. International Transactions in Operational Research, 26(3), 1135–1151. Crossref, Web of Science, Google Scholar
Wang, JB, M Liu, N Yin and P Ji (2017). Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects. Journal of Industrial and Management Optimization, 13(2), 1025–1039. Crossref, Web of Science, Google Scholar
Wang, JB and ZQ Xia (2005). Flow-shop scheduling with a learning effect. Journal of the Operational Research Society, 56(11), 1325–1330. Crossref, Web of Science, Google Scholar
Wang, XY, Z Zhou, X Zhang, P Ji and JB Wang (2013). Several flow shop scheduling problems with truncated position-based learning effect. Computers & Operations Research, 40(12), 2906–2929. Crossref, Web of Science, Google Scholar
Wu, CC and WC Lee (2008). Single-machine scheduling problems with a learning effect. Applied Mathematical Modeling, 32(7), 1191–1197. Crossref, Web of Science, Google Scholar
Wu, YB and JJ Wang (2016). Single-machine scheduling with truncated sum-of-processing-times-based learning effect including proportional delivery times. Neural Computing and Applications, 27(4), 937–943. Crossref, Web of Science, Google Scholar
Wu, CC, Y Yin and SR Cheng (2013). Single-machine and two-machine flowshop scheduling problems with truncated position-based learning functions. Journal of the Operational Research Society, 64(1), 147–156. Crossref, Web of Science, Google Scholar
Xu, J, CC Wu, Y Yin, C Zhao, YT Chiou and WC Lin (2016). An order scheduling problem with position-based learning effect. Computers & Operations Research, 74, 175–186. Crossref, Web of Science, Google Scholar