An Efficient Constructive Heuristic for Permutation Flow Shops to Minimize Total Flowtime

摘要

In this paper, FFC (Fast fiowtime-computing) is presented for fiowtime computing in flow shops. The CPU-time of an algorithm for flow shops can be reduced considerably by replacing classical flowtime computing with FFC based on the facts that FFC is faster than the classical one and that flowtime computing of schedules/partial schedules is the main computational burden of most algorithms for flow shops. This is illustrated by modifying RZ, one of the three best existing heuristics(FL, WY and RZ) for flowtime minimization, with FFC in which about half of the CPU-time is saved. An efficient constructive heuristic is proposed for permutation flow shops with flowtime minimization, of which the CPU-time is more than that of RZ but much less than those of FL and WY. Our proposal is compared with FL, WYand RZ in terms of ARPD (Average relative percentage deviation), STD (Standard deviation) and BEST (number of best solutions obtained for a given size of problems). Computational results show that the proposed heuristic outperforms WY and RZ, and also outperforms FL when job-machine ratio is small. However, as the ratio increases, the proposal will finally be outperformed by FL but needs far less CPU-time than FL does.