A memetic differential evolution algorithm for energy-efficient parallel machine scheduling. (January 2019)

• Record Type: Journal Article
• Authors: Wu, Xueqi; Che, Ada
• Is Part Of: Omega. Volume 82(2019)
• Page Start: 155
• Page End: 165
• Publication Date: 2019-01
• Subjects: Energy-efficient scheduling -- Unrelated parallel machines -- Memetic algorithm -- Differential evolution -- List scheduling; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2018.01.001
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: An unrelated parallel machine scheduling problem with a dynamic speed-scaling technique. An objective to minimize both makespan and total energy consumption. A new memetic differential evolution algorithm with speed adjusting and job swap heuristics. An adaptive meta-Lamarckian learning strategy for local search heuristics. Computational results show the proposed algorithm outperforms NSGA-II and SPEA-II. Abstract: This paper considers an energy-efficient bi-objective unrelated parallel machine scheduling problem to minimize both makespan and total energy consumption. The parallel machines are speed-scaling. To solve the problem, we propose a memetic differential evolution (MDE) algorithm. Since the problem involves assigning jobs to machines and selecting an appropriate processing speed level for each job, we characterize each individual by two vectors: a job-machine assignment vector and a speed vector. To accelerate the convergence of the algorithm, only the speed vector of each individual evolves and a list scheduling heuristic is applied to derive its job-machine assignment vector based on its speed vector. To further enhance the algorithm, we propose efficient speed adjusting and job-machine swap heuristics and integrate them into the algorithm as a local search approach by an adaptive meta-Lamarckian learning strategy. Computational results reveal that the incorporation of list scheduling heuristic and local search greatly strengthens the algorithm. Computational experiments also show that the proposed MDE algorithm outperforms SPEA-II and NSGA-II significantly.