Neighbourhood search-based metaheuristics for the bi-objective Pareto optimization of total weighted earliness-tardiness and makespan in a JIT single machine scheduling problem

• This paper proposes three neighbourhood search-based metaheuristics for the Pareto-based bi-objective optimization of total weighted earliness-tardiness (TWET) and makespan in single machine scheduling problem (SMSP). The problem environment allows idle times to be inserted in the schedules, resulting in a piecewise linear convex tradeoff curve between TWET and makespan objectives for a given sequence of jobs. • A timing algorithm is proposed to generate the optimal TWET-makespan tradeoff curve for each sequence of jobs. • Four different performance metrics are devised to compare the performance between the proposed metaheuristic algorithms. • The performance comparisons between the proposed neighbourhood-based metaheuristics and a population-based metaheuristic adopted from the literature revealed that a variant of the multiobjective variable neighbourhood descent approach, namely MOIVND, outperformed the other methods. • 3-job insertion neighbourhood structure and the backtrack-based perturbation operator used in MOIVND have significantly influenced its performance. This paper studies the simultaneous minimization of total weighted earliness-tardiness (TWET) and makespan in a just-in-time single-machine scheduling problem (JIT-SMSP) with sequence-dependent setup times and distinct due windows, allowing idle times in the schedules. Multiple variants of variable neighbourhood descent (VND) based metaheuristic algorithms are proposed to generate Pareto-optimal solutions for this NP-hard problem. An optimal timing algorithm (OTA) is presented that generates a piecewise linear convex trade-off curve between the two objectives for a given sequence of jobs. The trade-off curves corresponding to the sequences of jobs generated in the proposed metaheuristics are trimmed and merged using a Pareto front generation procedure to generate the Pareto-optimal front comprising line segments and points. The computational performance of the proposed VND-based metaheuristic algorithms is compared with state-of-the-art metaheuristic algorithms from the literature on test instances of varying sizes using four performance metrics devised to compare Pareto fronts comprising line segments and points. The performance comparisons reveal that a proposed variant of backtrack-based iterated VND with multiple neighbourhood structures outperforms the other algorithms in most performance metrics.