An Improvement of Total Flowtime and Makespan for the General Flow Shop Scheduling Problem Via O(n4m) Algorithm

Abstract

In general flowshop scheduling problems, n jobs are arranged on m machines in a series and follow the same routing. To obtain the best schedule, minimizing the flowtime and makespan in a general flow shop has been demonstrated. When the number of job little increases, the computational time to find the best schedule is time consuming or non-polynomial hard (NP-hard) in complexity. This study proposes a polynomial time heuristic, which is complex in O(n4m), to obtain the solution. From experimental instances (640), the results show that the proposed algorithm yields better performance in terms of the average relative percentage deviation in both flowtime and makespan values than the well-known Framinan and Leisten method, while its time complexity is the same.