Single-Machine Scheduling Problem with Precedence Constraints

The single-machine scheduling problem with precedence constraints without idle time is to sequence n jobs on a single-machine subject to precedence constraints among jobs, so that the objective value is minimized.

[TS13] S. Tanaka and S. Sato. An exact algorithm for the precedence-constrained single-machine scheduling problem. European Journal of Operational Research 229(2), pp. 345-352, 2013. DOI: 10.1016/j.ejor.2013.02.048

• total weighted tardiness
  • job data derived from OR-Library
    • [wt40.zip (n=40)] [wt50.zip (n=50)] [wt100.zip (n=100)]
  • precedence data
    • [wt40prec.zip (n=40)] [wt50prec.zip (n=50)] [wt100prec.zip (n=100)]
• total weighted earliness-tardiness
  • job data (earliness weights are added to OR-Library instances)
    • [wet40.zip (n=40)] [wet50.zip (n=50)] [wet100.zip (n=100)]
  • precedence data
    • [wet40prec.zip (n=40)] [wet50prec.zip (n=50)] [wet100prec.zip (n=100)]

• Job data

[number of jobs]

[processing time 1] [due date 1] [earliness weight 1 (if exists)] [tardiness weight 1]

[processing time 2] [due date 2] [earliness weight 2 (if exists)] [tardiness weight 2]

...

• precedence data

[predecessor 1] [successor 1]

[predecessor 2] [successor 2]

...

Optimal values and CPU times on a desktop computer with an Intel Core i7 960 CPU at 3.2GHz and 12GB RAM.

• total weighted tardiness
  • [wt40opt.xlsx (n=40)] [wt50opt.xlsx (n=50)] [wt100opt.xlsx (n=100)]
• total weighted earliness-tardiness
  • [wet40opt.xlsx (n=40)] [wet50opt.xlsx (n=50)] [wet100opt.xlsx (n=100)]