Online hierarchical parallel-machine scheduling in shared manufacturing to minimize the total completion time
研究了共享制造中m台相同机器上的在线分层调度问题，目标是总完工时间最小。工作按层级到达，低层级只能在前k台机器加工，高层级可在任意机器加工。提出了贪心算法并分析其竞争比，对k=1情形给出了改进算法。
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.