METAHEURISTICS FOR THE MIXED NO-IDLE FLOWSHOP SCHEDULING PROBLEM WITH DUE WINDOWS

The flowshop scheduling problem is present in the everyday context of many medium and large companies, due to limited resources and high demand. This paper addresses the mixed no-idle permutation flowshop scheduling (MNIPFS) problem, considering machines that can be idle and machines that cannot be idle. The objective is to determine the processing sequence of jobs in order to minimize the total weighted earliness and tardiness penalties, considering due windows. The problem is classified as NP-hard due to the high computational complexity associated with obtaining optimal solutions through exact methods. This paper proposes three approaches for the MNIPFS: a mixed integer linear programming (MILP) model and two metaheuristics, Iterated Greedy algorithm (IG) and Greedy Randomized Adaptive Search Procedure (GRASP). The metaheuristics were evaluated through computational experiments using a large set of instances, showing relevant performance in terms of solution quality and execution time.