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

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

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, (Formula presented.) 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 (Formula presented.) where (Formula presented.) Proposing a greedy algorithm, we show that its tight competitive ratio is (Formula presented.) 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 (Formula presented.) which is optimal for (Formula presented.) Numerical experiments show that the greedy online algorithm has good performance, especially when k approaches 1 or m.

Original languageEnglish
JournalJournal of the Operational Research Society
DOIs
Publication statusAccepted/In press - 2022

Keywords

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

ASJC Scopus subject areas

  • Modelling and Simulation
  • Statistics, Probability and Uncertainty
  • Strategy and Management
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Online hierarchical parallel-machine scheduling in shared manufacturing to minimize the total completion time'. Together they form a unique fingerprint.

Cite this