A New ILP Model for Identical Parallel-Machine Scheduling with Family Setup Times Minimizing the Total Weighted Flow Time by a Genetic Algorithm

Abstract

This paper presents a novel, integer-linear programming (ILP) model for an identical parallel-machine scheduling problem with family setup times that minimizes the total weighted flow time (TWFT). Some researchers have addressed parallel-machine scheduling problems in the literature over the last three decades. However, the existing studies have been limited to the research of independent jobs, and most classical optimization methods are focused on parallel-machine scheduling problems without considering setup times and relationship between jobs. This problem is shown to be NP-hard one in the strong sense. Obtaining an optimal solution for this type of complex, large-sized problems in reasonable computational time is extremely difficult. A meta-heuristic method, based on genetic algorithms, is thus proposed and applied to the given problem in order to obtain a good and near-optimal solution, especially for large sizes. Further, the efficiency of the proposed algorithm, based on various test problems, is compared with the Lingo 8.0 software.