A good balance for an online scheduling problem considering both learning and deteriorating effects in the handicraft process

Abstract

The paper considers an online scheduling problem with the effects of both learning and deterioration to minimize the total completion time. More specifically, we assume that the actual processing length of job J_j is $p_{\mathit{\text{jr}}}=p_j{r}^b+\mathit{\text{at}},$ where p_j is the initial processing time of J_j, t is the starting time of J_j, r is the seating arrangement position of J_j, b is the learning factor and a is the deterioration factor, respectively. For this problem, we show that the performance ratio of any deterministic online algorithm is not <2 and provide a best possible online algorithm DSBPT with a competitive ratio of 2. Furthermore, we also present a concise computational simulation study to verify the effectiveness and efficiency of the proposed algorithm DSBPT, as well as the management implications provided for decision-makers to production optimization.

Keywords:

• Scheduling
• online algorithm
• learning effects
• deteriorating effects
• handicraft

Author contributions

In this paper, the contributions of authors are as follows: Ran Ma: conceptualization, methodology, and the correctness of algorithm. Xiaohua Yang: editing paper, algorithm design, and analysis. Wenwen Han: digital simulation. Aijun Liu: the correctness of paper writing.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The work described in this paper is supported by the National Natural Science Foundation of China [grant number 11501171] and the Province Natural Science Foundation of Shandong [grant number ZR2020MA028].