The Estimation Distribution Algorithm for the Blocking Job Shop Scheduling Problem

The blocking job shop problem (BJSSP) is a variant of the classical job shop problem, where a job completed on one machine cannot be transferred to the next machine until the latter becomes available, causing the current machine to remain blocked. Many real-world problems have been modeled as BJSSP. This problem is classified as strongly NP-hard. The existing literature indicates that some proposed methods fail to guarantee the generation of feasible solutions during the search process, necessitating solution reconstruction. In this study, we developed an Estimation Distribution Algorithm (EDA) designed to operate strictly within the BJSSP feasible solution space. The experiments showed that no specific levels of the factors were found to be significant in determining the quality of the solutions found by the EDA across all problem sets. On the other hand, incorporating assignment probabilities into the construction of EDA solutions facilitated diversity among the generated solutions. The runtime of the EDA for the proposed problem sets in the experiments, using the factor levels defined, ranged from 20 s for problems with 10 jobs and 5 machines to 600 s for those with 30 jobs and 10 machines. The proposed EDA begins by generating a random initial population of solutions. The makespan (Cmax) is then computed for each individual. The next generation is composed by three sets of individuals. The first group corresponds to a percentage of the best-performing individuals of the current generation. The second group is generated by using a probability distribution function derived from the structure of the selected solutions, while the remaining individuals are created randomly to enhance the algorithm’s exploratory capability. Our results demonstrate that the proposed method improves upon some of the previously best-known results in the current state of the art.