A Minimizing Algorithm

IBM ILOG Scheduler User's Manual > Advanced Concepts > Scheduling with Unary Resources: the Job-Shop Problem > A Minimizing Algorithm

A Minimizing Algorithm

INDEX

PREVIOUS NEXT

As we indicated at the beginning of this chapter, this kind of problem is normally so difficult that we are going to tackle it in several different ways. Here, we'll give a minimizing algorithm. In Chapter 16, we develop an algorithm that uses a dichotomizing binary search for makespan. In Chapter 30, we explain how to use a "randomized" algorithm.

Solving an instance of the job-shop scheduling problem is equivalent to sequencing the activities optimally for each resource. The following algorithm, already highlighted in Chapter 14, can be used to order the activities.

Select a resource among the resources required by unranked activities.
Select the activity to execute first among the unranked activities that require the chosen resource. Post the corresponding precedence constraints. Keep the other activities as alternatives to be tried upon backtracking.
Iterate step 2 until all the activities that require the chosen resource have been put in order.
Iterate steps 1 to 3 until all the activities that require a common resource have been put in order.

As in Chapter 14, the predefined goal IloRankForward implements this algorithm. Arguments of this goal are a resource selector and a resource constraint selector. Again as in Chapter 14, we use the resource selector IloSelResMinGlobalSlack and the resource constraint selector IloSelFirstRCMinStartMax. The resource selector selects the resource on which not all activities are ordered and which has minimal slack according to the member function IlcUnaryResource::getGlobalSlack.

The resource constraint selector selects the resource constraint corresponding to the unranked activity with the minimal earliest start time and, in addition, the activity with the minimal latest start time when two or more activities have the same earliest start time.

Using the predefined goal IloRankForward, we can obtain an optimal solution to the problem by simply setting makespan as the objective variable to minimize.

    
    IloSolver solver(model);
    IloGoal goal = IloRankForward(env,
                                  makespan, 
                                  IloSelResMinGlobalSlack,
                                  IloSelFirstRCMinStartMax);
 
    if (solver.solve(goal)) 
      PrintSolution(solver, jobs, makespan);
    else {
      solver.out() << " Failure for Makespan " 
                   << solver.getMax(makespan) << endl;
    }
 
    solver.printInformation();
    env.end();
 
  } catch (IloException& exc) {
    cout << exc << endl;
  }

PREVIOUS NEXT