An effective iterated greedy algorithm for scheduling unrelated parallel batch machines with non-identical capacities and unequal ready times

• DOI: 10.1016/j.cie.2016.12.038
• Publication Date: 2017-01-09T15:31:34Z
• Authors: José Elias C. Arroyo; Joseph Y.-T. Leung
• Keywords: 0211 other engineering and technologies; 02 engineering and technology

We consider the problem of scheduling jobs on unrelated batch machines so as to minimize the makespan.We present a MIP formulation of the problem and present a lower bound on the optimal makespan.We propose an iterated greedy algorithm to solve the problem.We compare our algorithm with three meta-heuristics in the literature.Computational results show that our algorithm outperforms the other three for both small-size and large-size problems. This study addresses the problem of scheduling a set of n jobs with arbitrary job sizes and non-zero ready times on a set of m unrelated parallel batch machines with different capacities so as to minimize the makespan. Unrelated parallel machines is the most general case of parallel machine environments where each machine processes each job at a different speed. In the studied problem, each machine can process several jobs simultaneously as a batch as long as the machine capacity is not exceeded. The batch processing time and the batch ready time are respectively equal to the largest processing time and the largest ready time among all the jobs in the batch.In this paper, we first provide a lower bound for the problem and a mixed integer programming (MIP) model. To solve the problem, a meta-heuristic based on the iterated greedy (IG) algorithm is proposed. IG is a simple meta-heuristic which generates a sequence of solutions by iterating over a greedy constructive heuristic using destruction and construction operations. In the recent literature this meta-heuristic has been employed to solve a considerable number of combinatorial optimization problems. This is because IG is easy to implement and it often exhibits an excellent performance. The effectiveness of the proposed IG algorithm is evaluated and compared by computational experiments on a large benchmark of randomly generated instances. The obtained results indicate that the proposed algorithm has a superior performance compared to some meta-heuristic algorithms proposed for similar problems.