Efficient scheduling of jobs on dissimilar parallel machines using heuristic assisted metaheuristic techniques

This work proposes a novel no-wait time heuristic mechanism for identifying optimal schedules for scheduling problems using metaheuristic techniques. The heuristic me-chanism helps to reduce the idle time in a machine by shifting the starting time of the job near its release date. The proposed mechanism can be directly integrated with meta-heuristic techniques without performing any modifications to the techniques. The pro-posed heuristic mechanism is employed with fifteen metaheuristic techniques and tested the efficacy by solving twelve scheduling problems with minimization of total processing cost as the objective. The performance of all metaheuristic techniques was analyzed, with and without incorporating the heuristic mechanism. It is observed that the heuristic mechanism helped metaheuristic techniques to determine better schedules, whereas, without the heuristic mechanism, many of these techniques were unable to obtain even one feasible schedule in a complex problem. The inclusion of the proposed heuristic mechanism has provided up to 10% improvement in the fitness value of the best sche-dules. It also helped to identify multiple realizations of the optimal schedules with zero idle time. This study also analyzed the effect of tightening constraints for solving the scheduling model using metaheuristic techniques. The performance analysis of the techniques validated that the inclusion of horizon constraints does not benefit the me-taheuristic techniques in determining better solutions.(c) 2022 Institution of Chemical Engineers. Published by Elsevier Ltd. All rights reserved.

Automated summary

This work proposes a novel heuristic mechanism that reduces idle time in machines by adjusting the starting time of jobs, and integrates it with metaheuristic techniques to improve scheduling solutions.