Parallel Machines Scheduling Problem for Minimization of Maximum Lateness with Sequence-Dependent Setup Times

摘要

In this paper, the identical parallel machines scheduling problem with sequence-dependent setup times is studied. The objective is to minimize the maximum lateness of jobs. A new mixed integer mathematical programming model is developed for solving the problem optimally. Since the research problem is shown to be NP-complete, two metaheuristic algorithms based on Genetic Algorithm (GA) and Simulated Annealing (SA) are applied to solve the problem. Random test problems are generated in different sizes to evaluate the efficiency of the proposed metaheuristic algorithms. The optimal solutions by MIP model are reported for for the small size test problems. Computational results show that the proposed GA and SA algorithms can reach the optimal solutions for all of the proposed small size instances. For larger size test problems, the only an upper bound can be achieved by the MIP model. For these instances the proposed metaheuristic algorithms are converged to equal or better solutions than the upper bound of the MIP model in a significantly shorter time.