A two-machine flowshop scheduling heuristic with bicriteria objective

Abstract

This paper presents a O(N-2) heuristic algorithm to solve the two-machine flowshop scheduling with bicriteria objective to minimize the sum of makespan and total flow time. An integer programming model with N-2+2N variables and 3N constraints is also formulated to validate the performance of the heuristic scheduling algorithm proposed here. Experimental results demonstrate that the proposed algorithm can efficiently solve this problem with a high solution quality. Although the integer programming model provides the optimal solution, variables and constraints markedly increase when the number of jobs increases. Therefore, the optimal solution is not always attainable within the allowable time. The heuristic algorithm is much more practical in real world applications than the integer programming model.