A hybrid differential evolution algorithm with column generation for resource constrained job scheduling. (September 2019)

• Record Type: Journal Article
• Authors: Nguyen, Su; Thiruvady, Dhananjay; Ernst, Andreas T.; Alahakoon, Damminda
• Is Part Of: Computers & operations research. Volume 109(2019)
• Page Start: 273
• Page End: 287
• Publication Date: 2019-09
• Subjects: Scheduling -- Column generation -- Differential evolution; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.05.009
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A new parallelised differential evolution algorithm to locate multiple local optima for resource constrained job scheduling problems is proposed. A new efficient iterated greedy search algorithm is proposed to refine the solutions obtained by differential evolution. The experiments show improvements over the state-of-the-art hybrid algorithm in terms of upper bounds and convergence. A new benchmark dataset is developed for resource constrained job scheduling problems with a wide range of network complexity, resource utilisation, and sizes. Abstract: Resource constrained job scheduling problems are ubiquitous in real-world logistics and supply chain management. By solving these optimisation problems, organisations can efficiently utilise logistical resources and improve delivery performance. Because of their complexity, finding optimal solution is challenging. Existing solution methods based on integer programming and meta-heuristics have shown promising results for small instances but become less efficient when they are applied to large-scale instances with hundreds of jobs. This paper presents a new hybrid optimisation method that combines the power of differential evolution, iterated greedy search, mixed integer programming, and parallel computing to solve resource constrained job scheduling problems. The experimental results with existing benchmark datasets and a set of 1755 newly generated instances show that the proposed algorithm can find high quality solutions even for hard instances. For small and medium instances, the optimality gaps of the proposed algorithms are significantly better than those of the mixed integer programming solver and the column generation algorithm. For large instances, the proposed algorithms can find solutions with significantly better upper bounds as compared to existing meta-heuristics and the state-of-the-art hybrid algorithm. The analyses also confirm the advantage of using multiple processing cores to improve the efficiency and solution quality of the proposed algorithm.