Minimizing the Sum of Maximum Earliness and Tardiness on Identical Parallel Machines Scheduling Problem

This paper addresses the problem of minimizing the sum of maximum earliness and tardiness on identical parallel machines scheduling problem. Each job has a processing time and a due date. Since this problem is trying to minimize and diminish the values of earliness and tardiness, the results can be useful for just–in-time production systems. It is shown that the problem is NP-hard. Using efficient lower and upper bounds and dominance rules based on adjacent pair-wise interchanges, a branch-and-bound algorithm is proposed. Then, large sizes problems were solved by two evolutionary meta-heuristic algorithms, genetic Algorithm and particle Swarm Optimization based on permutation and priority approaches. In order to evaluate the efficiency of the branch and bound algorithm, 1920 instances were randomly generated in small and medium sizes. Also, the proposed heuristic and metaheuristic algorithms are then tested on 4880 randomly generated problems varying from small to large sizes. The results indicate that the branch & bound method is efficient in solving small and medium sized problems optimally with up to 20 jobs and 5 machines, and also the presented genetic algorithm is efficient in tackling problems of any size.