A two-agent single-machine scheduling problem with late work criteria

作者：Wang, Du-Juan; Kang, Chao-Chung; Shiau, Yau-Ren; Wu, Chin-Chia; Hsu, Peng-Hsiang^*

来源：Soft Computing, 2017, 21(8): 2015-2033.

DOI：10.1007/s00500-015-1900-5

• Scheduling
• Two agent
• Dynamic programming
• Branch-and-bound algorithm

This paper addresses a two-agent scheduling problem where the objective is to minimize the total late work of the first agent, with the restriction that the maximum lateness of the second agent cannot exceed a given value. Two pseudo-polynomial dynamic programming algorithms are presented to find the optimal solutions for small-scale problem instances. For medium- to large-scale problem instances, a branch-and-bound algorithm incorporating the implementation of a lower bounding procedure, some dominance rules and a Tabu Search-based solution initialization, is developed to yield the optimal solution. Computational experiments are designed to examine the efficiency of the proposed algorithms and the impacts of all the relative parameters.

• 出版日期2017-4
• 单位大连理工大学