An Optimal Online Algorithm for Scheduling with Learning Consideration

Ran Ma, Wenwen Han, Cuixia Miao () and Juan Zou ()
Additional contact information
Ran Ma: School of Management Engineering, Qingdao University of Technology, Qingdao 266525, P. R. China2University Research Center for Smart City, Construction and Management of Shandong, Province, Qingdao 266525, P. R. China
Wenwen Han: School of Management Engineering, Qingdao University of Technology, Qingdao 266525, P. R. China2University Research Center for Smart City, Construction and Management of Shandong, Province, Qingdao 266525, P. R. China
Cuixia Miao: School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China
Juan Zou: School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2021, vol. 38, issue 05, 1-17

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 Jj is a non-increasing function of its position h, i.e., pjh = pjαh−1, where pj is the basic processing time of job Jj and 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: Scheduling; learning effect; online algorithm; competitive ratio (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595921400029
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:38:y:2021:i:05:n:s0217595921400029

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595921400029

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().