View article

We study the scheduling problem of minimising weighted completion times on parallel identical batching machines with dynamic job arrivals and incompatible job families. Each job is associated with a family, weight (priority), release time, and size. Batching machines can process simultaneously up to a specified total size of the jobs of a particular family. The scheduling problem can be represented by . We present a mathematical model and heuristic algorithms employing different local search procedures individually and sequentially under a variable neighbourhood search scheme. We have shown that among local searches, repositioning the batches instead of jobs yields better results. The best-performing heuristic algorithm is capable of generating solutions within 0.6% of the best overall heuristic solution for each instance in a reasonable amount of time. When this heuristic is compared against the …