Single‐machine scheduling with dynamic arrivals: Decomposition results and an improved algorithm
研究了工件到达时间不同的单机动态调度问题，目标是总完工时间最小。通过分解将大问题拆解为小问题求解，并改进了现有分支定界算法的效率。
This article considers the single-machine dynamic scheduling problem where the jobs have different arrival times and the objective is to minimize the sum of completion times. This problem is known to be strongly NP-hard. We develop decomposition results for this problem such that a large problem can be solved by combining optimal solutions for several smaller problems. The decomposition results can be used with any implicit enumeration method to develop an optimal algorithm. Our computational experiment indicates that the computational efficiency of the currently best available branch-and-bound algorithm can be improved with the use of our decomposition results. © 1996 John Wiley & Sons, Inc.