Minimizing makespan in three-machine flow shops with deteriorating jobs |
| |
Authors: | Ji-Bo Wang Ming-Zheng Wang |
| |
Affiliation: | 1. School of Science, Shenyang Aerospace University, Shenyang 110136, China;2. School of Management Science and Engineering, Dalian University of Technology, Dalian 116024, China |
| |
Abstract: | In this paper, a three-machine permutation flow shop scheduling problem with time-dependent processing times is considered. By the time-dependent processing times we mean that the job's processing time is an increasing function of its starting time. The objective is to find a sequence that minimizes the makespan. This problem is well known to be NP-hard. Several dominance properties and a lower bound are derived to speed up the elimination process of a branch-and-bound algorithm. Moreover, two heuristic algorithms are proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational experiments on randomly generated problems are conducted to evaluate the branch-and-bound algorithm and heuristic algorithm. Computational results show that the proposed heuristic algorithm M-NEH perform effectively and efficiently. |
| |
Keywords: | Scheduling Flow shop Deteriorating jobs Makespan Branch-and-bound algorithm Heuristic algorithm |
本文献已被 ScienceDirect 等数据库收录! |