Paper #63
Constructive heuristics and simulated annealing for identical parallel machine scheduling with DeJong learning effect and interval wise energy limits
Presenting author: Moaaz Saed Al Shehadat
Session: O11
Abstract
This paper studies an identical parallel-machine scheduling problem with DeJong’s learning effect and interval-wise energy limits. Each job has a nominal processing time and a power rate. Processing times are position dependent and decrease according to DeJong’s learning model, while the total energy consumption within each interval must remain below a predefined limit. The objective is to minimize the makespan while maintaining energy feasibility. Three constructive heuristics are considered: Modified Longest Time First (MLTF), Modified Shortest Time First (MSTF), and Random Scheduling (RS). In addition, Simulated Annealing (SA) is applied as an improvement method initialized from the feasible MLTF schedule. The computational study is based on a benchmark of 5760 generated instances. The methods are evaluated using number of wins, average relative gap, and runtime. Computational results show that SA achieved the strongest overall performance, obtaining 3072 wins (53.34% win rate) and the lowest average relative gap of 0.035976. Among the constructive heuristics, MSTF achieved the strongest baseline performance.