Meta-heuristic algorithms for scheduling on parallel batch machines with unequal job ready times

摘要

This paper address the problem of scheduling a set of jobs with non-zero ready times and incompatible job families on a set of identical parallel batch machines so as to minimize the total weighted tardiness. In this problem, each machine can process several jobs of a same family simultaneously as a batch as long as the machine capacity is not exceeded. Jobs of a family has the same processing time and the batch ready time is equal to the largest ready time among all the jobs in the batch. To solve the problem, we propose two meta-heuristic algorithms based on Iterated Greedy (IG) and Simulated Annealing (SA), respectively. The performance of our algorithms is evaluated and compared by computational experiments on a large benchmark of instances from the literature. The obtained results indicate that the proposed algorithms has good performance compared to two meta-heuristic algorithms proposed for the same problem.