HEURISTIC APPROACH FOR SOLVING FLOW SHOP MACHINE SCHEDULING PROBLEMS

Abstract

The problem of scheduling n jobs on m flow shop machines to maximize the (weighted) number of Just-In-Time jobs is considered. It is known that this problem is NP-Complete even for a single machine, indicating that no efficient optimal solution can be found in reliable time for even fairly large instance problems. In this research, two greedy heuristic solutions are proposed and compared with an optimum solution found by Xpress-MP using small problem instances. Computational results and analysis for various scales of instances show that the greedy heuristic algorithms performed creditably well when compared with an optimal solution using small problem instances. The quality and efficiency of the heuristics coupled with solutions to large instance problems are highlighted.