Two-machine flow shop scheduling with linear decreasing job deterioration

作者：Wang Ji Bo^*; Liu Li Li

来源：Computers & Industrial Engineering, 2009, 56(4): 1487-1493.

DOI：10.1016/j.cie.2008.09.020

• Scheduling
• Flow shop
• Deteriorating jobs
• Total completion time
• Branch-and-bound algorithm
• Heuristic algorithm

In this paper, we consider a two-machine flow shop scheduling problem with deteriorating jobs. By a deteriorating job, we mean that the processing time is a decreasing function of its execution start time. A proportional linear decreasing deterioration function is assumed. The objective is to find a sequence that minimizes total completion time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and some lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational results for randomly generated problem instances are presented, which show that the heuristic algorithm effectively and efficiently in obtaining near-optimal solutions.

• 出版日期2009-5
• 单位上海第二工业大学; 沈阳航空航天大学