Chinese Journal of Computers   Full Text
Title	Heuristics for the No-Wait Flow Shop Problem with Makespan Criterion
Authors	PAN Quan-Ke1),2) ZHAO Bao-Hua1) QU Yu-Gui1)
Address	1)(Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027) 2)(School of Computer Science, Liaocheng University, Liaocheng, Shandong 252059)
Year	2008
Issue	No.7(1147—1154)
Abstract &   Background	Abstract This paper aims at finding a permutation of jobs for the no-wait flow shop (NWFS) scheduling problem with the objective of minimizing makespan. First, after investigating the property of the solution of NWFS, a speed-up method with the computational complexity O(n) is developed for calculating the makespan of a permutation. Second, a discrete particle swarm optimization algorithm (DPSO) is presented for solving this problem. Two kinds of neighborhood, insert neighborhood and multi-insert neighborhood consisting of multi-insert, which performs several inserts simultaneously in a single iteration of algorithm, are fused in the algorithm to balance the exploration and exploitation. A short-cut for insert neighborhood is also proposed. Third, an anomaly in NWFS is studied where increasing processing time of some operations may decrease makespan. Several theorems about this anomaly are reported, and an improvement procedure by slowing down some machines is designed for a permutation. Last, computational tests based on the well known benchmark suites in the literature show that the presented DPSO is effective and efficient on finding optimum or near-optimal solutions, and that slowing down some machines may result in significant reduction of the makespan yielded by DPSO. Keywords no-wait flow shop; makespan; particle swarm optimization; neighborhood search; anomaly Background Production scheduling plays a key role in the manufacturing systems of enterprises for maintaining a competitive position in fast-changing markets, so it is very important to develop effective, efficient and advanced manufacturing and scheduling technologies and approaches. No-wait flow shop scheduling problem is one of the most important scheduling problems, which has important applications in different industries including chemical processing, food processing, concrete ware production, and pharmaceutical processing. In the past decades, most research focused on developing heuristic algorithms for this problem. Particle swarm optimization (PSO) algorithm is one of the latest metaheuristic methods in the literature. However, the applications of PSO algorithm on combinatorial optimization problems are still considerably limited. The major obstacle of successfully applying PSO algorithm to combinatorial problems is due to its continuous nature. To remedy this drawback, Pan, Tasgetiren & Liang presented a novel variant of PSO algorithm, called DPSO algorithm. In this paper, the authors apply DPSO to solve the no-wait flow shop scheduling problem with makespan criterion and propose an improvement procedure by slowing down some machines for a permutation. Computational tests show the effectiveness and efficiency of the presented method. This research is partially supported by National Science Foundation of China under grants 90104010 and Postdoctoral Science Foundation of China under grants 20070410791. The work group have published more than 60 papers in this field, and most of them have been cited by SCI/EI. This paper deepens research theory and contribute to the two projects.