Minimising makespan for two batch-processing machines with non-identical job sizes in job shop

Abstract

In this article, the job shop scheduling problem with two batch-processing machines is considered. The machines have limited capacity and the jobs have non-identical job sizes. The jobs are processed in batches and the total size of each batch cannot exceed the machine capacity. The processing times of a job on the two machines are proportional. We show the problem of minimising makespan is NP-hard in the strong sense. Then we provide an approximation algorithm with worst-case ratio no more than 4, and the running time of the algorithm is O(n log n). Finally, the performance of the proposed algorithm is tested by different levels of instances. Computational results demonstrate the effectiveness of the algorithm for all the instances.

Keywords:

• batch processing machines
• non-identical job sizes
• job shop
• approximation algorithm

Acknowledgements

We would like to thank the editor-in-chief and the anonymous referees for providing constructive comments on an earlier version of this article. This study is supported by National High-Tech Research and Development Program of China under grant no. 2009AA043403, National Natural Science Foundation of China under grant numbers 71071045, 70631003, 70801024 and 71001031 and the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant 20100111120015.