Article ID Journal Published Year Pages File Type
1135503 Computers & Industrial Engineering 2009 7 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Engineering Industrial and Manufacturing Engineering
Authors
, ,