Minimizing makespan in a no-wait flowshop with two batch processing machines using estimation of distribution algorithm

Abstract

This paper studies the problem of minimising makespan in a no-wait flowshop with two batch processing machines (comprised of a parallel batch processing machine and a serial batch processing machine), non-identical job sizes and unequal ready times. We propose a population-based evolutionary method named estimation of distribution algorithm (EDA). Firstly, the individuals in the population are coded into job sequences. Then, a probabilistic model is built to generate new population and an incremental learning method is developed to update the probabilistic model. Thirdly, the best-fit heuristic is used to group jobs into batches and a least idle/waiting time approach is proposed to sequence the batches on batch processing machines. In addition, some problem-dependent local search heuristics are incorporated into the EDA to further improve the searching quality. Computational simulation and comparisons with some existing algorithms demonstrate the effectiveness and robustness of the proposed algorithm. Furthermore, the effectiveness of embedding the local search method in the EDA is also evaluated.

Keywords:

• scheduling
• no-wait flowshop
• batch processing machines
• makespan
• estimation of distribution algorithm (EDA)

Notes

This work was supported by the National Natural Science Foundation of China [grant number 71171184]. This research also received funding from the University of Tennessee Health Information Technology & Simulation (HITS) Laboratory.

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [No. 71171184]. This research also received funding from the University of Tennessee Health Information Technology & Simulation (HITS) Laboratory.