scheduling_tutorial

Scheduling concurrent jobs for several machines

(example adapted from Differential Evolution in Discrete Optimization by Daniel Lichtblau)

A department needs to run certain programs daily. They have access to a fixed number of machines (homogeneous machines, so each job time is independent of machine used) and have good approximations for the run time of each program.

These times are only approximate and moreover we want a schedule that is robust (in the sense that a failure of some assumption such as program time will not do too much damage). Typically one might augment them by a modest percentage; we will simply assume that has already been done and take our set of job times as given.

Our variables will be the starting times for each job; the total time period will be one day.

const int n_jobs = 50;
std::vector<std::chrono::hours> job_duration(n_jobs);

int main()
{
  std::generate(job_duration.begin(), job_duration.end(),
                []
                {
                  return std::chrono::hours(random::between(1, 4));
                });

  de_problem prob(n_jobs, {-0.5, 23.5});
}

The random range for starting times is slightly larger than the feasible one ([0.0, 23.0]). This is intentional and improves DE results.

Two alternatives to specify the parameters of the problem are:

de_problem prob({{-0.5, 23.5}, ... {-0.5, 23.5}});

or, in equivalent manner:

de_problem prob;

// Problem's parameters.
for (unsigned i(0); i < n_jobs; ++i)
  prob.insert( range(-0.5, 23.5) );

Both forms are more flexible since they allow to use a different range for each parameter.

An obvious constraints is that all jobs start at a nonnegative time and that they start more than their length prior to the 24 hour limit.

So a first approximation of our objective function is:

double f(std::vector<double> start)
{
  double ret(0.0);

  for (unsigned i(0); i < start.size(); ++i)
  {
    if (start[i] < 0.0)
      ret += start[i];

    const auto end(start[i] + job_duration[i].count());
    if (end >= 24.0)
      ret -= end - 24.0;
  }

  return ret
}

Moreover we are not allowed to have more jobs than available machines at any one time. To check this we must test, at each starting time, that there is at least one machine free.

This is coded as follows. We have a summation constraint for every job variable. The sum is over all other jobs. Each contributes a value of one precisely if it starts before and ends after the start time of the one under consideration, else zero. It is these sums, one such for each job, that must be at least one less than the total number of machines.

double f(std::vector<double> start)
{
  double ret(0.0);

  for (unsigned i(0); i < start.size(); ++i)
  {
    // ...

    int occupied(1);
    for (unsigned j(0); j < start.size(); ++j)
    if (j != i &&
        start[j] <= start[i] &&
        start[j] + job_duration[j].count() > start[i])
      ++occupied;

    if (occupied > n_machines)
      ret -= occupied - n_machines;
  }

  return ret;
}

DE was originally formulated in the context of continuous optimization, but here we must enforce integrality.

For this there are (at least) two viable approaches. One is to allow variables to take on values in a continuum, but use penalty functions to push them toward integrality.

For example, one could add, for each variable start[i], a penalty term of the form std::pow(start[i] - std::round(start[i]), 2.0) (perhaps multiplied by some suitably large constant).

Another method, the one actually used here, is to explicitly round all (real-valued) variables before evaluating in the objective function (experience indicates this is typically the more successful approach).

So after the last touch the objective function is:

double f(std::vector<double> start)
{
  double ret(0.0);

  for (auto &s : start)
    s = std::round(s);

  for (unsigned i(0); i < start.size(); ++i)
  {
    // A job starts at a nonnegative time.
    if (start[i] < 0.0)
      ret += start[i];

    // A job starts more than its length prior to the 24 hour limit.
    const auto end(start[i] + job_duration[i].count());
    if (end >= 24.0)
      ret -= end - 24.0;

    int occupied(1);
    for (unsigned j(0); j < start.size(); ++j)
      if (j != i &&
          start[j] <= start[i] &&
          start[j] + job_duration[j].count() > start[i])
        ++occupied;

    if (occupied > n_machines)
      ret -= occupied - n_machines;
  }

  return ret;
}

We generated 50 jobs of random time lengths from 1 to 3 hours. We allow five machines and have a full 24 hour period. The scheduling is by no means trivial.

int main()
{
  std::generate(job_duration.begin(), job_duration.end(),
                []
                {
                  return std::chrono::hours(random::between(1, 4));
                });

  std::cout << "Total time required: "
            << std::accumulate(job_duration.begin(), job_duration.end(),
                               std::chrono::hours(0)).count()
            << '\n';

  de_problem prob(n_jobs, {-0.5, 23.5});
  prob.env.individuals =  250;
  prob.env.generations = 2000;

  de_search<decltype(f)> search(prob, f);

  const auto res(search.run().best.solution);

  for (unsigned i(0); i < n_jobs; ++i)
    std::cout << i << ' ' << std::round(res[i]) << ' '
              << job_duration[i].count() << '\n';
}

The full source for this example is contained in the examples/scheduling.cc file.

The eventual solution (graph above) meets all the constraints. Time is the horizontal axis. The vertical axis simply records which of the jobs is being shown at that height. In simple geometric terms, the number of active jobs at a given time is found by slicing with a vertical line and counting the number of horizontal bars hit.