A fast flowtime-computing procedure and its applications to heuristics for flow shops with flowtime minimization

FFC (fast flowtime-computing) is presented for flowtime computing in flow shops. Generally, FFC is faster than the classical flowtime computing procedure in which all jobs should be calculated. Because computing flowtimes of schedules/partial schedules is the Main computational burden of most algorithms for flow shops, the CPU-time of an algorithm can be reduced considerably by replacing flowtime-computing with FFC. FFC is utilized to modify FL, WY and RZ, three best existing constructive heuristics for permutation flow shops with flowtime minimization. Analysis results reveal that CPU-times of the three modified heuristics can be saved by about 33.3%, 50% and 50% of those of FL, WY and RZ respectively, which is valuable for practical flow shops with large sizes.