Single machine job sequencing with a restricted common due window

Shih Wei Lin, Kuo Ching Ying*, Wen Jie Wu, Chen Yang Cheng

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

2 Scopus citations


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.

Original languageEnglish
Article number8861316
Pages (from-to)148741-148755
Number of pages15
JournalIEEE Access
StatePublished - 2019
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2013 IEEE.


  • Backtracking
  • Common due window
  • Scheduling
  • Simulated annealing
  • Single machine


Dive into the research topics of 'Single machine job sequencing with a restricted common due window'. Together they form a unique fingerprint.

Cite this