A branch population genetic algorithm for dual-resource constrained job shop scheduling problem

• Published in: Computers & industrial engineering 2016-12, Vol.102, p.113-131
• Main Authors: Li, Jingyao, Huang, Yuan, Niu, Xinwei
• Format: Article
• Language: English
• Subjects: Algorithms; Branch population; Compressed time window; Constraints; Dual resource constrained; Evolution; Genetic algorithm; Genetic algorithms; Job shop scheduling; Markov chain; Mathematical models; Operators; Scheduling
• ISSN: 0360-8352; 1879-0550
• DOI: 10.1016/j.cie.2016.10.012

•The branch population can strengthen population diversity and accelerate convergence.•The elite evolutionary operator is utilized to optimize search ability.•The sector roulette selection operator can decrease the computational complexity.•The strategy on compressed time window can improve the scheduling performance.•According to the Markov chain theory, BPGA can weakly converge to the Pareto front. The manufacturing systems constrained by both machines and heterogeneous workers are referred to as Dual Resource Constrained (DRC) systems. DRC scheduling problem has attracted more and more attention in recent years. In order to address the Dual Resource Constrained Job Shop Scheduling Problem (DRCJSP) to minimize the makespan and cost, a meta-heuristic algorithm named Branch Population Genetic Algorithm (BPGA) is proposed in this paper. The proposed algorithm is a genetic algorithm (GA) based scheduling approach, and it introduces the branch population to accumulate and transfer evolutionary experience of parent chromosomes via pheromone. The branch population can strengthen the population diversity and accelerate convergence. Additionally, several mechanisms are applied to optimize the performance of BPGA. The elite evolutionary operator is utilized to optimize search ability by laying particular emphasis on the evolution of the elite population. The roulette selection operator based on sector segmentation is proposed to decrease the computational complexity and avoid the algorithm prematurity. The scheduling strategy based on compressed time window is proposed to improve the global scheduling performance. In our research, BPGA shows convergence to the Pareto front according to the Markov chain theory. Numerical experiments with randomly generated examples and case studies are analyzed to evaluate the performance of the proposed algorithm. Computational experiments show BPGA can provide the promising results for the DRCJSP.