Chinese Journal of Computers   Full Text
Title	Objective Increment Based Iterative Greedy Heuristic for No-Wait Flowshops with Total Flowtime Minimization
Authors	ZHU Xia LI Xiao-Ping WANG Qian`
Address	(School of Computer Science and Engineering, Southeast University, Nanjing 210096) (Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 210096)
Year	2009
Issue	No.1(132—141)
Abstract &   Background	Abstract No-wait flowshops with total flowtime minimization are typical NP-Complete combinatorial optimization problems, widely existing in practical manufacturing systems. Different from traditional methods in which objectives are completely computed for a new generated schedule, objective increment methods are presented in this paper. Whether a new schedule is better or worse than the original one is judged just by the objective increment, which can reduce computational time considerably. Objective increment properties are analyzed for fundamental operations of heuristics. Based on the properties, two fundamental methods are introduced for fast evaluating schedules. FIG (Fast Iterative Greedy algorithm) is proposed for the considered problem, which includes initial solution generating and solution improvement phases. Besides an initial solution generating method being constructed, a segment based reconstructive heuristic and an iterative improvement procedure are developed for local and global search respectively to improve the current solution. FIG is compared with PH1p, SRTS and DPSOvnd algorithms on 110 traditional benchmark instances. Computational results show that FIG outperforms SRTS and PH1p but a little worse than DPSOvnd in effectiveness. In efficiency, FIG is better than SRTS and DPSOvnd but a little worse than PH1p. Keywords no-wait flowshops; objective increment; heuristic; total flowtime minimization Background The aim of this work is to propose an effective and efficient heuristic algorithm for total flowtime minimization in no-wait flowshop problems. This work is supported mainly by the National Natural Science Foundation of China under grant No.60504029 called “objective increment based composite heuristics for large scale no-wait flowshops”. It focuses on no-wait flowshop probems (NWFPs for short) which are important kind of constrained flowshop problems. In NWFPs, the operations of each job have to be continuously processed. No interruption is permitted either on or between machines. NWFPs widely exist in metallurgy, plastic molding, chemical processing and food processing industries. Modern manufacturing systems such as JIT systems, flexible manufacturing environments and robotic cells can also be modeled as NWFPs. The optimization objective in NWFPs can be modeled as the weighted sum of “distance” of adjacent jobs in a sequence. The “distance” is related only to the processing times of the related adjacent jobs but independent on other jobs in the sequence. Hence, it can be predetermined. Whether a new generated schedule is better or not than the original one can be judged just by calculating the sum of all the objective increments by the change of job positions, instead of calculating all time parameters of jobs in the whole schedule. Therefore, the time complexity of algorithms can be reduced. Objective increment properties are analyzed for fundamental operations of heuristics. Based on the properties, two fundamental methods are introduced for evaluating schedules fast. A fast iterated greedy algorithm FIG is proposed. In FIG, an initial solution generating method is constructed, and then a segment based reconstruction strategy and an iterative improvement procedure are developed for local and global search respectively to improve the current solution. In addition, an SA-like acceptance criterion is adopted to escape from local optimal. Experimental results show that, FIG outperforms PH1p and SRTS algorithms but it is little worse than DPSOvnd algorithm on effectiveness. On efficiency, FIG is better than SRTS and DPSOvnd but a little worse than PH1p. Therefore, FIG may be suitable for large scale NWFPs. This work is also supported by the National Natural Science Foundation of China under grant No.60672092 and the National High Technology Research and Development Program　(863 Program) of China under grant No.2008AA04Z103.