Algorithms For Batch Scheduling Problems With Arbitrary-size Jobs

Production with batch-processing machines and arbitrary-size jobs is an important production scheduling problem. In this mode, jobs have arbitrary sizes and are processed in batches on machines as long as the total size of jobs in a batch does not exceed the machine capacity. The processing of a batch cannot be interrupted until all the jobs in the batch are completed. we consider the scheduling problem of a batching machine with different jobs, to research how to optimize the production process with different conditions of machines, and to teduce the production costs. we hope our research may help improve the actual production and Improve production efficiency.First, this paper consider the scheduling problem of a batching machine with jobs of multiple families. Jobs from different families cannot be processed in a batch. We present a mixed integer programming model for the problems. Then we propose two polynomial time heuristics based on longest processing time first rule and first fit rule. For the general case, we show the performance guarantee of the methods for the two objectives respectively. Then We consider a class of scheduling problems where jobs have arbitrary size jobs. Jobs are processed on parallel batch-processing machines with fixed capacity given that the total size of jobs in a batch cannot exceed the machine capacity. The objective is to minimize the weighted sum of makespan and total production cost. We present the integer programming model and analyze the computational complexity of the problem. We propose a lower bound of the optimal solutions. Then we provide an improved ant colony optimization (IACO) to solve the problem. A new candidate list is proposed according to the batching rules to reduce the number of feasible solutions and running time of the algorithm. Finally, different scales of instances are designed in the experiment and the solutions of IACO are compared with lower bounds of optimal solutions. The running times are also reported for all the instances. The results show the effectiveness of our proposed algorithm. Finally, we summary the content of this paper, and prospect the future research direction.