job-shop.cpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.dev>
 *
 *  Copyright:
 *     Christian Schulte, 2019
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.dev
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */
 
#include <gecode/driver.hh>
 
#include <gecode/int.hh>
#include <gecode/minimodel.hh>
 
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
 
using namespace Gecode;
 
/*
 * The paper uses ideas from: D. Grimes and E. Hebrard, Solving Variants
 * of the Job Shop Scheduling Problem through Conflict-Directed Search,
 * INFORMS Journal of Computing, Volume 27, Issue 2, 2015.
 *
 * Warning: this solution is a sketch and not competitive as not all
 * techniques from the paper have been implemented.
 *
 */

namespace JobShopConfig {
  static const bool verbose = false;

  static const unsigned int probes = 50U;
  static const unsigned int fail_probe = 10000U;

  static const unsigned int time_probe  = 30U * 1000U;
  static const unsigned int time_adjust = 30U * 1000U;
  static const unsigned int time_solve  = 60U * 1000U;

  static const double restart_scale = 5000.0;
  static const double restart_base = 1.3;
}
 
// Instance data
namespace {
 
  // Instances
  extern const int* js[];
  // Instance names
  extern const char* name[];

  class Spec {
  protected:
    const int* data;
    int l, u;
    const char* n;
  public:
    bool valid(void) const {
      return data != nullptr;
    }
    int jobs(void) const {
      return data[0];
    }
    int machines(void) const {
      return data[1];
    }
    int machine(int i, int j) const {
      return data[2 + i*machines()*2 + j*2];
    }
    int duration(int i, int j) const {
      return data[2 + i*machines()*2 + j*2 + 1];
    }
  protected:
    static const int* find(const char* s) {
      for (int i=0; ::name[i] != nullptr; i++)
        if (!strcmp(s,::name[i]))
          return js[i];
      return nullptr;
    }
    int clower(void) const {
      int l = 0;
      Region r;
      int* mach = r.alloc<int>(machines());
      for (int j=0; j<machines(); j++)
        mach[j]=0;
      for (int i=0; i<jobs(); i++) {
        int job = 0;
        for (int j=0; j<machines(); j++) {
          mach[machine(i,j)] += duration(i,j);
          job += duration(i,j);
        }
        l = std::max(l,job);
      }
      for (int j=0; j<machines(); j++)
        l = std::max(l,mach[j]);
      return l;
    }
    int cupper(void) const {
      int u = 0;
      for (int i=0; i<jobs(); i++)
        for (int j=0; j<machines(); j++)
          u += duration(i,j);
      return u;
    }
  public:
    Spec(const char* s) : data(find(s)), l(0), u(0), n(s) {
      if (valid()) {
        l = clower(); u = cupper();
      }
    }
    int lower(void) const {
      return l;
    }
    int upper(void) const {
      return u;
    }
    const char* name(void) const {
      return n;
    }
  };
 
}

class JobShopOptions : public InstanceOptions {
private:
  Driver::BoolOption _verbose;
  Driver::UnsignedIntOption _probes;
  Driver::UnsignedIntOption _fail_probe;
  Driver::UnsignedIntOption _time_probe;
  Driver::UnsignedIntOption _time_adjust;
  Driver::UnsignedIntOption _time_solve;
  Driver::DoubleOption _tbf;
public:
  JobShopOptions(const char* s)
    : InstanceOptions(s),
      _verbose("verbose","whether to print schedule",
               JobShopConfig::verbose),
      _probes("probes","how many probes to perform",
              JobShopConfig::probes),
      _fail_probe("fail-probe","failure limit per probe",
                  JobShopConfig::fail_probe),
      _time_probe("time-probe","time-out for probing (in milliseconds)",
                   JobShopConfig::time_probe),
      _time_adjust("time-adjust","time-out for adjusting (in milliseconds)",
                   JobShopConfig::time_adjust),
      _time_solve("time-solve","time-out for solving (in milliseconds)",
                  JobShopConfig::time_solve),
      _tbf("tbf", "tie-breaking factor", 0.0) {
    add(_verbose);
    add(_probes);
    add(_fail_probe);
    add(_time_probe);
    add(_time_adjust);
    add(_time_solve);
    add(_tbf);
  }

  bool verbose(void) const {
    return _verbose.value();
  }

  unsigned int probes(void) const {
    return _probes.value();
  }

  unsigned int fail_probe(void) const {
    return _fail_probe.value();
  }

  unsigned int time_probe(void) const {
    return _time_probe.value();
  }

  unsigned int time_adjust(void) const {
    return _time_adjust.value();
  }

  unsigned int time_solve(void) const {
    return _time_solve.value();
  }

  double tbf(void) const {
    return _tbf.value();
  }

  virtual void help(void) {
    InstanceOptions::help();
    std::cerr << "\tAvailable instances:" << std::endl << "\t\t";
    for (int i=1; ::name[i] != nullptr; i++) {
      std::cerr << ::name[i] << ", ";
      if (i % 4 == 0)
        std::cerr << std::endl << "\t\t";
    }
    std::cerr << std::endl;
  }
};
 

class JobShopBase : public IntMinimizeScript {
protected:
  const JobShopOptions& opt;
  const Spec spec;
  IntVarArray start;
  IntVar makespan;
public:
  JobShopBase(const JobShopOptions& o)
    : IntMinimizeScript(o), opt(o), spec(opt.instance()),
      start(*this, spec.machines() * spec.jobs(), 0, spec.upper()),
      makespan(*this, spec.lower(), spec.upper()) {
    // Number of jobs and machines/steps
    int n = spec.jobs(), m = spec.machines();
    // Endtimes for each job
    IntVarArgs end(*this, n, 0, spec.upper());
 
    // Precedence constraints and makespan
    for (int i=0; i<n; i++) {
      for (int j=1; j<m; j++)
        rel(*this, start[i*m+j-1] + spec.duration(i,j) <= start[i*m+j]);
      rel(*this, start[i*m+m-1] + spec.duration(i,m-1) <= makespan);
    }
  }

  void nooverload(void) {
    // Number of jobs and machines/steps
    int n = spec.jobs(), m = spec.machines();
 
    IntVarArgs jobs(m*n);
    IntArgs dur(m*n);
 
    for (int i=0; i<n; i++)
      for (int j=0; j<m; j++) {
        jobs[spec.machine(i,j)*n+i] = start[i*m+j];
        dur[spec.machine(i,j)*n+i] = spec.duration(i,j);
      }
 
    for (int j=0; j<m; j++) {
      IntVarArgs jpm(n);
      IntArgs dpm(n);
      for (int i=0; i<n; i++) {
        jpm[i] = jobs[j*n+i]; dpm[i] = dur[j*n+i];
      }
      unary(*this, jpm, dpm);
    }
  }

  virtual IntVar cost(void) const {
    return makespan;
  }

  JobShopBase(JobShopBase& s)
    : IntMinimizeScript(s), opt(s.opt), spec(s.spec) {
    start.update(*this, s.start);
    makespan.update(*this, s.makespan);
  }

  virtual void
  print(std::ostream& os) const {
    os << "\t\t" << spec.name()
       << " [makespan: " << makespan << "]" << std::endl;
    if (opt.verbose()) {
      // Number of jobs
      int n = spec.jobs();
      // Number of machines/steps
      int m = spec.machines();
      for (int i=0; i<n; i++) {
        os << "\t\t\t[" << i << "]: ";
        for (int j=0; j<m; j++)
          os << start[i*m+j] << "  ";
        os << std::endl;
      }
    }
  }
};

class CommonOptions : public Search::Options {
public:
  CommonOptions(const JobShopOptions& opt) {
    clone = false;
    threads = opt.threads();
    c_d = opt.c_d();
    a_d = opt.a_d();
    nogoods_limit = opt.nogoods() ? opt.nogoods_limit() : 0U;
  }
};

class JobShopProbe : public JobShopBase {
public:
  JobShopProbe(const JobShopOptions& o)
    : JobShopBase(o) {
    nooverload();
  }
  void branch(unsigned int p, Rnd r) {
    switch (p) {
    case 0U:
      Gecode::branch(*this, start, INT_VAR_MIN_MIN(), INT_VAL_MIN());
      break;
    case 1U:
      Gecode::branch(*this, start, INT_VAR_MAX_MIN(), INT_VAL_MIN());
      break;
    case 2U:
      Gecode::branch(*this, start, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
      break;
    case 3U:
      Gecode::branch(*this, start, tiebreak(INT_VAR_MIN_MIN(),
                                            INT_VAR_RND(r)), INT_VAL_MIN());
      break;
    case 4U:
      Gecode::branch(*this, start, tiebreak(INT_VAR_MAX_MIN(),
                                            INT_VAR_RND(r)), INT_VAL_MIN());
      break;
    default:
      if (p & 1U)
        Gecode::branch(*this, start, INT_VAR_RND(r), INT_VAL_MIN());
      else
        Gecode::branch(*this, start, INT_VAR_RND(r), INT_VAL_SPLIT_MIN());
      break;
    }
    assign(*this, makespan, INT_ASSIGN_MIN());
  }

  JobShopProbe(JobShopProbe& s)
    : JobShopBase(s) {}

  virtual Space*
  copy(void) {
    return new JobShopProbe(*this);
  }
};

class JobShopSolve : public JobShopBase {
protected:
  BoolVarArray sorder;
  IntSharedArray fst;
  IntSharedArray snd;
  IntAFC iafc;
  double afc(BoolVar x, int i) const {
    return ((x.afc() + start[fst[i]].afc() + start[snd[i]].afc()) /
            (start[fst[i]].size() + start[fst[i]].size()));
  }

  static double afcmerit(const Space& home, BoolVar x, int i) {
    return static_cast<const JobShopSolve&>(home).afc(x,i);
  }

  IntAction iaction; BoolAction baction;
  double action(int i) const {
    return ((baction[i] + iaction[fst[i]] + iaction[snd[i]]) /
            (start[fst[i]].size() + start[fst[i]].size()));
  }

  static double actionmerit(const Space& home, BoolVar, int i) {
    return static_cast<const JobShopSolve&>(home).action(i);
  }

  IntCHB ichb; BoolCHB bchb;
  double chb(int i) const {
    return ((bchb[i] + ichb[fst[i]] + ichb[snd[i]]) /
            (start[fst[i]].size() + start[fst[i]].size()));
  }

  static double chbmerit(const Space& home, BoolVar, int i) {
    return static_cast<const JobShopSolve&>(home).chb(i);
  }

  Rnd rnd;
public:
  enum {
    BRANCH_AFC,    
    BRANCH_ACTION, 
    BRANCH_CHB     
  };
  enum {
    PROP_ORDER, 
    PROP_UNARY  
  };
  JobShopSolve(const JobShopOptions& o)
    : JobShopBase(o),
      sorder(*this, spec.machines()*spec.jobs()*(spec.jobs()-1)/2, 0, 1),
      rnd(o.seed()) {
    if (opt.propagation() == PROP_UNARY)
      nooverload();
 
    // Number of jobs and machines/steps
    int n = spec.jobs(), m = spec.machines();
 
    fst.init(m*n*(n-1)/2);
    snd.init(m*n*(n-1)/2);
 
    IntArgs jobs(m*n), dur(m*n);
 
    for (int i=0; i<n; i++)
      for (int j=0; j<m; j++) {
        jobs[spec.machine(i,j)*n+i] = i*m+j;
        dur[spec.machine(i,j)*n+i] = spec.duration(i,j);
      }
 
    int l=0;
    for (int j=0; j<m; j++) {
      for (int i1=0; i1<n; i1++)
        for (int i2=i1+1; i2<n; i2++) {
          if (dur[j*n+i1] > dur[j*n+i2]) {
            order(*this,
                  start[jobs[j*n+i1]], dur[j*n+i1],
                  start[jobs[j*n+i2]], dur[j*n+i2],
                  sorder[l]);
            fst[l] = j*n+i1; snd[l] = j*n+i2;
          } else {
            order(*this,
                  start[jobs[j*n+i2]], dur[j*n+i2],
                  start[jobs[j*n+i1]], dur[j*n+i1],
                  sorder[l]);
            fst[l] = j*n+i2; snd[l] = j*n+i1;
          }
          l++;
        }
      assert(l == (j+1)*n*(n-1)/2);
    }
 
    double tbf = opt.tbf();
    switch (opt.branching()) {
    case BRANCH_AFC:
      iafc.init(*this,start,opt.decay());
      if (tbf > 0.0) {
        auto tbl =
          [tbf] (const Space&, double w, double b) {
          assert(b >= w);
          return b - (b - w) * tbf;
        };
        branch(*this, sorder, tiebreak(BOOL_VAR_MERIT_MAX(&afcmerit,tbl),
                                       BOOL_VAR_RND(rnd)),
               BOOL_VAL_MIN());
      } else {
        branch(*this, sorder, BOOL_VAR_MERIT_MAX(&afcmerit),
               BOOL_VAL_MIN());
      }
      break;
    case BRANCH_ACTION:
      iaction.init(*this,start,opt.decay());
      baction.init(*this,sorder,opt.decay());
      if (tbf > 0.0) {
        auto tbl =
          [tbf] (const Space&, double w, double b) {
          assert(b >= w);
          return b - (b - w) * tbf;
        };
        branch(*this, sorder, tiebreak(BOOL_VAR_MERIT_MAX(&actionmerit,tbl),
                                       BOOL_VAR_RND(rnd)),
               BOOL_VAL_MIN());
      } else {
        branch(*this, sorder, BOOL_VAR_MERIT_MAX(&actionmerit),
               BOOL_VAL_MIN());
      }
      break;
    case BRANCH_CHB:
      ichb.init(*this,start);
      bchb.init(*this,sorder);
      if (tbf > 0.0) {
        auto tbl =
          [tbf] (const Space&, double w, double b) {
          assert(b >= w);
          return b - (b - w) * tbf;
        };
        branch(*this, sorder, tiebreak(BOOL_VAR_MERIT_MAX(&chbmerit,tbl),
                                       BOOL_VAR_RND(rnd)),
               BOOL_VAL_MIN());
      } else {
        branch(*this, sorder, BOOL_VAR_MERIT_MAX(&chbmerit),
               BOOL_VAL_MIN());
      }
      break;
    }
    assign(*this, start, INT_VAR_MIN_MIN(), INT_ASSIGN_MIN());
    assign(*this, makespan, INT_ASSIGN_MIN());
  }

  JobShopSolve(JobShopSolve& s)
    : JobShopBase(s), sorder(s.sorder), fst(s.fst), snd(s.snd),
      iafc(s.iafc), iaction(s.iaction), baction(s.baction),
      ichb(s.ichb), bchb(s.bchb), rnd(s.rnd) {}

  virtual Space*
  copy(void) {
    return new JobShopSolve(*this);
  }
};

class FailTimeStop : public Search::Stop {
protected:
  Search::FailStop* fs; 
  Search::TimeStop* ts; 
public:
  FailTimeStop(unsigned int fail, unsigned int time)
      : fs(new Search::FailStop(fail)),
        ts(new Search::TimeStop(time)) {}

  virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
    return fs->stop(s,o) || ts->stop(s,o);
  }

  bool fail(const Search::Statistics& s, const Search::Options& o) const {
    return fs->stop(s,o);
  }

  bool time(const Search::Statistics& s, const Search::Options& o) const {
    return ts->stop(s,o);
  }

  ~FailTimeStop(void) {
    delete fs; delete ts;
  }
};

void
print(const Search::Statistics& stat, bool restart) {
  using namespace std;
  cout << "\t\t\tnodes:      " << stat.node << endl
       << "\t\t\tfailures:   " << stat.fail << endl;
  if (restart)
    cout << "\t\t\trestarts:   " << stat.restart << endl
         << "\t\t\tno-goods:   " << stat.nogood << endl;
  cout << "\t\t\tpeak depth: " << stat.depth << endl;
}

void
solve(const JobShopOptions& opt) {
  Rnd rnd(opt.seed());
 
  /*
   * Invariant:
   *  - There is a solution with makespan u,
   *  - There is no solution with makespan l
   */
 
  int l, u;
 
  {
    Support::Timer t; t.start();
    Search::Statistics stat;
    JobShopProbe* master = new JobShopProbe(opt);
 
    if (master->status() != SS_SOLVED) {
      delete master;
      std::cerr << "Error: has no solution..." << std::endl;
      return;
    }
 
    l = master->cost().min();
    u = master->cost().max();
 
    FailTimeStop fts(opt.fail_probe(),opt.time_probe());
    CommonOptions so(opt);
    so.stop = &fts;
    bool stopped = false;
 
    std::cout << "\tProbing..." << std::endl;
 
    std::cout << "\t\tBounds: [" << l << "," << u << "]"
              << std::endl;
 
    for (unsigned int p=0; p<opt.probes(); p++) {
      JobShopProbe* jsp = static_cast<JobShopProbe*>(master->clone());
      jsp->branch(p,rnd);
      DFS<JobShopProbe> dfs(jsp,so);
      JobShopProbe* s = dfs.next();
      Search::Statistics statj = dfs.statistics();
 
      if (s != nullptr) {
        if (u > s->cost().val()) {
          u = s->cost().val();
          s->print(std::cout);
        }
        delete s;
      } else if (fts.time(statj,so)) {
        stopped = true;
        break;
      }
      stat += statj;
    }
    delete master;
 
    print(stat,false);
    std::cout << "\t\t\truntime:    ";
    Driver::stop(t,std::cout);
    std::cout << std::endl;
 
    if (stopped) {
      std::cout << "\t\t\t\tstopped due to time-out..." << std::endl;
    }
  }
 
  std::cout << std::endl << "\tAdjusting..." << std::endl;
 
  // Dichotomic search
  {
    JobShopSolve* master = new JobShopSolve(opt);
 
 
    if (master->status() == SS_FAILED) {
      delete master;
      std::cerr << "Error: has no solution..." << std::endl;
      return;
    }
 
    {
      Support::Timer t; t.start();
      Search::Statistics stat;
      CommonOptions so(opt);
      if (opt.time_adjust() > 0U)
        so.stop = Search::Stop::time(opt.time_adjust());
      bool stopped = false;
      while (l < u) {
        std::cout << "\t\tBounds: [" << l << "," << u << "]"
                  << std::endl;
        JobShopSolve* jss = static_cast<JobShopSolve*>(master->clone());
        int m = (l + u) / 2;
        rel(*jss, jss->cost() >= l);
        rel(*jss, jss->cost() <= m);
        so.cutoff = Search::Cutoff::geometric(JobShopConfig::restart_scale,
                                              JobShopConfig::restart_base);
        RBS<JobShopSolve,DFS> rbs(jss,so);
        JobShopSolve* s = rbs.next();
 
        stat += rbs.statistics();
 
        if (s != nullptr) {
          s->print(std::cout);
          u = s->cost().val();
          delete s;
        } else if (rbs.stopped()) {
          stopped = true;
          break;
        } else {
          l = m+1;
        }
      }
 
      print(stat,true);
      std::cout << "\t\t\truntime:    ";
      Driver::stop(t,std::cout);
      std::cout << std::endl;
 
      if (stopped) {
        std::cout << "\t\t\t\tstopped due to time-out..." << std::endl;
      }
 
    }
 
    if (l == u) {
      delete master;
      std::cout << std::endl
                << "\tFound best solution and proved optimality."
                << std::endl;
      return;
    }
 
 
    {
      Support::Timer t; t.start();
      std::cout << std::endl << "\tSolving..." << std::endl;
 
      rel(*master, master->cost() >= l);
      rel(*master, master->cost() < u);
 
      CommonOptions so(opt);
      if (opt.time_solve() > 0U)
        so.stop = Search::Stop::time(opt.time_solve());
      so.cutoff = Search::Cutoff::geometric(JobShopConfig::restart_scale,
                                            JobShopConfig::restart_base);
      RBS<JobShopSolve,BAB> rbs(master,so);
      while (JobShopSolve* s = rbs.next()) {
        s->print(std::cout);
        u = s->cost().val();
        delete s;
      }
 
      print(rbs.statistics(),true);
      std::cout << "\t\t\truntime:    ";
      Driver::stop(t,std::cout);
      std::cout << std::endl;
 
      if (rbs.stopped()) {
        std::cout << "\t\t\t\tstopped due to time-out..." << std::endl;
        std::cout << std::endl
                  << "\tSolution at most ";
        double a = (static_cast<double>(u-l+1) / u) * 100.0;
        std::cout << std::setprecision(2) << a
                  << "% away from optimum."
                  << std::endl;
 
      } else {
        std::cout << std::endl
                  << "\tFound best solution and proved optimality."
                  << std::endl;
      }
    }
 
  }
}
 
 
 
 

int
main(int argc, char* argv[]) {
  JobShopOptions opt("JobShop");
 
  opt.branching(JobShopSolve::BRANCH_AFC);
  opt.branching(JobShopSolve::BRANCH_AFC, "afc");
  opt.branching(JobShopSolve::BRANCH_ACTION, "action");
  opt.branching(JobShopSolve::BRANCH_CHB, "chb");
 
  opt.propagation(JobShopSolve::PROP_UNARY);
  opt.propagation(JobShopSolve::PROP_ORDER,"order");
  opt.propagation(JobShopSolve::PROP_UNARY,"unary");
 
  opt.instance("ft06");
 
  opt.restart_base(JobShopConfig::restart_base);
  opt.restart_scale(JobShopConfig::restart_scale);
  opt.nogoods(true);
 
  opt.parse(argc,argv);
  if (!Spec(opt.instance()).valid()) {
    std::cerr << "Error: unknown instance" << std::endl;
    return 1;
  }
  solve(opt);
  return 0;
}
 
#include "examples/job-shop-instances.hpp"
 
// STATISTICS: example-any