A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan

2016/11/11 by Onur Ozturk, Onur Öztürk, Mehmet A. Begen +1
Engineering · Computer Science · #Scheduling and Optimization Algorithms #Optimization and Packing Problems #Optimization and Search Problems

paper · doi:10.1080/00207543.2016.1253889

Abstract

In this paper, we present a branch and bound algorithm for the parallel batch scheduling of jobs having different processing times, release dates and unit sizes. There are identical machines with a fixed capacity and the number of jobs in a batch cannot exceed the machine capacity. All batched jobs are processed together and the processing time of a batch is given by the greatest processing time of jobs in that batch. We compare our method to a mixed integer program as well as a method from the literature that is capable of optimally solving instances with a single machine. Computational experiments show that our method is much more efficient than the other two methods in terms of solution time for finding the optimal solution.

Related

• Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job families
• Efficient algorithms for scheduling equal-length jobs with processing set restrictions on uniform parallel batch machines
• Improved algorithms for single machine serial-batch scheduling to minimize makespan and maximum cost
• Batch scheduling in differentiation flow shops for makespan minimisation
• Parallel Batch Scheduling With Incompatible Job Families Via Constraint Programming