Two-machine flow shop scheduling with linear decreasing job deterioration

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2008.09.020 Byline: Ji-Bo Wang (a), Li-Li Liu (b) Keywords: Scheduling; Flow shop; Deteriorating jobs; Total completion time; Branch-and-bound algorithm; Heuristic algorithm Abstract: 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. Author Affiliation: (a) School of Science, Shenyang Institute of Aeronautical Engineering, Shenyang 110136, People's Republic of China (b) School of Science, Shanghai Second Polytechnic University, Shanghai 201209, People's Republic of China Article History: Received 23 March 2008; Revised 10 September 2008; Accepted 12 September 2008 Article Note: (footnote) [star] This manuscript was processed by Area Editor Maged M. Dessouky.