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

Qi Wei, Yong Wu, T. C. E. Cheng, Fengxin Sun and Yiwei Jiang

Journal of the Operational Research Society, 2023, vol. 74, issue 11, 2432-2454

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≤k≤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{1m−k+1,max{2k⌈s⌉+3k+2m+4⌈s⌉,2k⌊s⌋+3k+2m+4⌊s⌋}}, where s=2m+4k. Proposing a greedy algorithm, we show that its tight competitive ratio is 1+2(m−k)km((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{2⌈2m+4⌉+2m+4⌈2m+4⌉+3,2⌊2m+4⌋+2m+4⌊2m+4⌋+3}, which is optimal for 2≤m≤5. Numerical experiments show that the greedy online algorithm has good performance, especially when k approaches 1 or m.

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2022.2150576 (text/html)
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:taf:tjorxx:v:74:y:2023:i:11:p:2432-2454

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2022.2150576

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().