Two-machine flow shop scheduling with linear decreasing job deterioration |
| |
Authors: | Ji-Bo Wang Li-Li Liu |
| |
Affiliation: | aSchool of Science, Shenyang Institute of Aeronautical Engineering, Shenyang 110136, People’s Republic of China;bSchool of Science, Shanghai Second Polytechnic University, Shanghai 201209, People’s Republic of China |
| |
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. |
| |
Keywords: | Scheduling Flow shop Deteriorating jobs Total completion time Branch-and-bound algorithm Heuristic algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|