Online hierarchical parallel-machine scheduling in shared manufacturing to minimize the total completion time

Abstract

We consider online hierarchical scheduling on m identical machines in shared manufacturing to minimize the total completion time. Each job has a unit-size processing time. The jobs arrive one by one and must be assigned to one of the m machines before the next job arrives. The jobs with a lower hierarchy can only be processed on the first k machines, $1\le k\le m-1,$ and the jobs with a higher hierarchy can be processed on any one of the m machines. We first show that the lower bound of the problem is at least $1+\min \{\frac{1}{m-k+1},\max \{\frac{2}{k\lceil s\rceil +3k+\frac{2m+4}{\lceil s\rceil }},\frac{2}{k\lfloor s\rfloor +3k+\frac{2m+4}{\lfloor s\rfloor }}\left\}\right\},$ where $s=\sqrt{\frac{2m+4}{k}}.$ Proposing a greedy algorithm, we show that its tight competitive ratio is $1+\frac{2(m-k)k}{m(\sqrt{(4m-3k)k}+k)}$ by analyzing a set of instances that must contain a worst-case instance, which is different from the general method of calculating the competitive ratio. In addition, for the case where k = 1, we present an improved online algorithm with a tight competitive ratio of $1+\max \{\frac{2}{\lceil \sqrt{2m+4}\rceil +\frac{2m+4}{\lceil \sqrt{2m+4}\rceil }+3},\frac{2}{\lfloor \sqrt{2m+4}\rfloor +\frac{2m+4}{\lfloor \sqrt{2m+4}\rfloor }+3}\},$ which is optimal for $2\le m\le 5.$ Numerical experiments show that the greedy online algorithm has good performance, especially when k approaches 1 or m.

Keywords:

• Share manufacturing
• hierarchical scheduling
• online algorithm
• competitive ratio

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported in part by the National Social Science Foundation of China under grant number 19BGL001, Natural Science Foundation of Zhejiang Province of China under grant number LY19A010002 and LY20A010021, Natural Science Foundation of Ningbo of China under grant number 2021J235 and 2021J147, Regional Open Cooperation and Free Trade Zone Research Base which is a Key Social Science Research Base of Ningbo of China, and the Contemporary Business and Trade Research Center of Zhejiang Gongshang University, which is a key Research Institute of Social Sciences and Humanities of the Ministry of Education of China. Cheng was supported in part by The Hong Kong Polytechnic University under the Fung Yiu King—Wing Hang Bank Endowed Professorship in Business Administration.