Test Instances for the Dynamic Single-machine Sequencing Problem to Minimize Total Weighted Completion Time

Problem: 1|rj|ΣwjCj

Parameter Values
n 20,30,...200
rj U(0,50.5nR), R=0.2, 0.4, 0.6, 0.8, 1.0, 1.25, 1.5, 1.75, 2.0, 3.0
pj U(1,100)
wj U(1,10)

* U(a,b) denotes an integer uniform random number on the interval [a,b].

Relevant Files:

Name Memo

Size (KB)
instances.zip random instances, uncompress to get “instances.txt” 1,173
dwct_generator.cpp c++ source file used to generate “instances.txt” 2
opt.zip optimal values (or best lower and upper bounds) of the test instances 23.8

 

Reference(s):

Paper that first reported experimental results on these instances:

Y. Pan and L. Shi 2005. New hybrid optimization algorithms for machine scheduling problems. To appear in IEEE Trans. Automation Science & Engineering. Available online through Optimization-Online.

Other papers (not a complete list) that deal with computational aspects of 1|rj|ΣwjCj:

  1. van den Akker, J. M. and C. A. J. Hurkens and M. W. P. Savelsbergh 2000. Time-indexed Formulations for Machine Scheduling Problems: Column Generation. INFORMS J. Comput. 12, 111-124.
  2. van den Akker, J. M. and van Hoesel, C. P. M. and Savelsbergh, M. W. P. 1999. A Polyhedral Approach to Single-Machine Scheduling Problems. Math. Program. 85, 541-572.
  3. Savelsbergh, M. W. P. and Uma, R. N. and Wein, J. 2005. NFORMS J. Comput. An Experimental Study of {LP}-Based Approximation Algorithms for Scheduling Problems. 17, 123-136.

Finally, if you think that your work is pertinent to computational issues that arise in solving 1|rj|ΣwjCj, feel free to drop me a line at yunpeng.pan@gmail.com; I'd be more than happy to enrich my list with the inclusion of your work.

(Last updated by Yunpeng Pan: 01/27/07)