Single-Machine Total Weighted Tardiness Problem with Sequence-Dependent Setup Times

The single-machine total weighted tardiness problem with sequence-dependent setup times is to find an optimal sequence of jobs to be processed on a single machine that minimizes the total weighted tardiness while considering setup times between jobs. Here, "sequence-dependent" means that the setup time is determined by the last processed job and the job to be processed next.

[TA13] S. Tanaka and M. Araki. An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. Computers & Operations Research 40(1), pp. 344-352, 2013. DOI: 10.1016/j.cor.2012.07.004

• Benchmark set by Cicirello [C07]
  • [external link]

[C07] V.A. Cicirello. The challenge of sequence-dependent setups: Proposal for a scheduling competition track on one machine sequencing problems. Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS) Workshop on Scheduling a Scheduling Competition, 2007.