CuSPLIB: A Library of Single-Machine Cumulative Scheduling Problems

Consider the following optimization problem: we are given n jobs, a time horizon T, and one machine M with processing capacity Cap >= 2. Each job has a processing time (pj), release date (rj), due date (dj), machine utilization (cj), and weight (wj). We would like to schedule all the jobs on machine M while making sure that: (i) all jobs obey their execution window [rj,dj] (to a certain extent; see possible objectives), and (ii) we respect the machine capacity at all times (i.e., given a time 0 <= t <= T, the sum of cj over all jobs running at time t is always less than or equal to Cap). Possible objective functions are: minimize makespan, minimize total (weighted) tardiness, minimize total number of late jobs, minimize total (weighted) delay, etc.

(Near cusp image courtesy of Prof. Curtis T. McMullen)
(Cusp and algebraic curve entries on Wikipedia)


WHAT'S NEW?  CuSPLIB Update Log (modified 06/02/11)

Our goal is to provide a library of challenging cumulative scheduling problems (CuSPs) that would motivate the study, development, and improvement of optimization algorithms dedicated to solving these problems. We provide a random instance generator, instances created by this generator, and additional instances created by other researchers. (If you'd like to contribute instances to CuSPLIB, send me an e-mail.) The general (raw) format of our instances is:

n T Cap
pj rj dj cj wj

The first line contains the number of jobs (n), time horizon (T), and machine capacity (Cap). That line is followed by n lines formatted as the second line above: processing time (pj), followed by release date (rj), etc. Our instance generator was written in Perl to facilitate execution across platforms. Its usage instructions are printed to the screen as shown below:

geninst.pl: CuSPLIB Random Instance Generator v1.0

Usage: geninst.pl <m> <n> <T> <Cap> <cmin> <cmax> <wmin> <wmax> <pmin> <pmax> <mode>
where:
        m = number of instances to generate (< 1000)
        n = number of jobs
        T = length of time horizon
      Cap = machine capacity
cmin,cmax = job sizes in % of Cap (uniformly drawn)
wmin,wmax = job windows in % of T (uniformly drawn)
pmin,pmax = job durations in % of their windows (uniformly drawn)
emin,emax = job weights (uniformly drawn)
     mode = type of output (1=ZIMPL, 2=OPL, 3=raw)

Job sizes are uniformly drawn between cmin% and cmax% of Cap; the width of job execution windows are uniformly drawn between wmin% and wmax% of T; job durations are uniformly drawn between pmin% and pmax% of the width of their respective execution windows; and job weights are uniformly drawn between emin and emax. All parameters are integer numbers. The mode parameter indicates the output type: raw is the format described above; ZIMPL mode creates a data file suitable for a model written in the ZIMPL language (click here for a partial ZIMPL code to read the generated data file); similarly, OPL mode creates a data file suitable for a model written in the ILOG OPL language (click here for a partial OPL code to be used with the generated data file).



Instance Generators



CuSP Instances

Instances generated with geninst.pl will be indentified by their generation parameters and (optionally) by a random generation seed (to allow for replication).



Integer Programming Formulations for CuSPs

Time-Indexed Formulation:

One of the most popular formulations of CuSPs discretizes the time horizon into time units:

C++ program using ILOG Concert technology:  cumulative.cpp. This program reads data files in the raw format and implements both the min makespan and min delay objectives (selected through a command-line parameter; see source file for details). It is also set up to output the model in .LP format into a file called cumulative.lp.

ZIMPL models:  minimize makespanminimize total weighted delay. These models assume that the data file is called csched.dat. To generate the corresponding LP file (suitable for use with most modern IP solvers), simply run the following command (replacing "model.zpl" by the appropriate file name): zimpl model.zpl.


Event-Based Formulations :

These formulations try to overcome the variable explosion of the time-indexed formulation by using the concept of "events" (e.g. the start and end of a job) and by avoiding time-related subscripts. However, this usually comes at the expense of weaker linear relaxations (more details to come).



Frequently Asked Questions

  1. I don't like your instance generator. Do you mind if I modify it?

    Of course not! Modifications and improvements are very welcome. Please send me the modified code so that I can make it available on this web site. If you have your own instance generator, I hope you'll be willing to share it with us.

  2. I've generated some CuSP instances that seem to be pretty tough to solve. How do I share them with other people?

    If you format your instances according to our raw file format and send them to me, I'll be happy to add them to CuSPLIB. After all, that's the whole point of this initiative! Please let me know how they were generated. If you used an instance generator posted on this web site, let me know what parameter values were used when generating the instances (if you can make your instance generator available, that's even better).

  3. I've improved some of the results published on CuSPLIB. How do I get credit for it?

    That's great! If you've found a better feasible solution, please send me the solution and its objective value. If you've improved a lower bound, just let me know what the new bound is. In both cases, it would be great if you could also provide some documentation explaining the methodology/algorithms used.

  4. How do I cite CuSPLIB?

    You can use the following BibTeX entry:

    @Misc{cusplib,
        author = {T. Yunes},
        title = {{CuSPLIB} 1.0: A Library of Single-Machine Cumulative Scheduling P
    roblems},
        howpublished = {{\tt http://moya.bus.miami.edu/\raisebox{-0.6ex}{\~{ }}tallys/cusplib/}},
        year = {2009},
    }



Comments and Feedback

I hope that CuSPLIB can become a useful resource to the academic community. Regardless of whether you're working on Integer Programming, Constraint Programming, heuristic, or hybrid methods for cumulative scheduling, this web site could become a meeting point where we exchange ideas and results with the common goal of advancing the state-of-the-art on CuSPs. Your comments, suggestions and feedback are always welcome. Feel free to drop me a line.



To Appear...


eXTReMe Tracker