Evaluating the Impact of Initial Solutions on Multi-objective Metaheuristics for a Bi-objective Job Scheduling Problem with Sequence-dependent Machine Deterioration

This paper investigates the impact of different initial solution strategies on the performance of multi-objective metaheuristics applied to a bi-objective job scheduling problem with sequence-dependent machine deterioration. The problem considers the allocation and sequencing of jobs on unrelated parallel machines, where each processed job reduces machine performance and increases the processing time of subsequent jobs. Two conflicting objectives are simultaneously addressed: minimizing the makespan and the total delay time. Four initial population strategies were evaluated in five widely used multi-objective algorithms under different generation limits. The results show that problem-oriented strategies, especially those guided by total delay time and makespan criteria, can improve solution quality and accelerate convergence. These findings highlight the importance of calibrating initial populations as a relevant component in the design and application of multi-objective metaheuristics for scheduling problems with deterioration.