Earliness-tardiness scheduling with distinct due dates

Preprint

Code

The code contains a branch-and-bound and a heuristic (iterated search) to solve the earliness-tardiness scheduling problems with distinct due dates and release dates.

It can be compiled with MSVC7 (with etresrelax.vcproj) and with gcc (with /bin/makefile).

Syntax:

Usage : etresrel.exe command arguments
  generate nbJobs releaseFactor tardinessFactor rangeFactor
  timing filename
  heur filename [number of runs]
  bnb filename [UB]
  lb filename

Download

Instances

Format:

NumberOfJobs
p1 r1 d1 alpha1 beta1
p2 r2 d2 alpha2 beta2
...
pn rn dn alphan betan

• Our instances [zip file] Instances with 20, 30 and 40, 50 jobs and no release dates.
  Our results (branch-and-bound and heuristic) in OpenDocument Spreadsheed or in Microsoft Excel.
  NEWS: All these instances are now solved by a new version of the branch-and-bound algorithm. The code and tables will be available soon!
• Similar instances with
  • 30, 60 and 90 jobs in a zip file
  • 120 and 150 jobs in another zip file
• Instances of Kerem Bülbül, Philip Kaminsky and Candice Yano [zip file]. Instances with release dates and up to 200 jobs.
  Our results (heuristic and lower bound) in OpenDocument Spreadsheed or in Microsoft Excel.

Works based on these instances

• Shunji Tanaka has just solved (in March 2008) these instances with up to 200 jobs.
• Self-Adapting Large Neighborhood Search: Application to single-mode scheduling problems by Ph. Laborie and D. Godard (ILOG)
• Contact me to list any other work.

Acknowledgments