Single Machine Job Sequencing With a Restricted Common Due Window

Abstract

This article deals with the problem of sequencing $N$ jobs on a single machine with a restrictive common due window. The objective is to minimize the total weighted earliness-tardiness penalties, which conform to just-in-time (JIT) manufacturing. A novel backtracking simulated annealing (BSA) algorithm with a backtracking mechanism and an effective coding scheme is proposed herein to solve this problem. The performance of the proposed BSA algorithm is compared with that of the best available algorithm and the simulated annealing (SA) algorithm using four benchmark problem sets. The computational results reveal that the backtracking mechanism can improve the performance of the SA algorithm and make the proposed BSA algorithm outperform the state-of-the-art algorithm. The proposed BSA algorithm is sufficiently efficient to satisfy the real-world scheduling requirements of the JIT manufacturing system.

Keywords

• Scheduling
• single machine
• common due window
• simulated annealing
• backtracking