Minimizing makespan in a no-wait flowshop with two batch processing machines using estimation of distribution algorithm. Issue 16 (17th August 2016)

• Record Type: Journal Article
• Authors: Zhou, Shengchao; Li, Xueping; Chen, Huaping; Guo, Cong
• Is Part Of: International journal of production research. Volume 54:Issue 16(2016)
• Page Start: 4919
• Page End: 4937
• Publication Date: 2016-08-17
• Subjects: scheduling -- no-wait flowshop -- batch processing machines -- makespan -- estimation of distribution algorithm (EDA); Factory management -- Periodicals; 658.57
• DOI: 10.1080/00207543.2016.1140920
• Languages: English
• ISSNs: 0020-7543

Abstract

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.