Delft University of Technology
Faculty Mechanical, Maritime and Materials Engineering
Transport Technology / Logistic Engineering



F.C. van Lookeren Campagne Methoden voor paarsgewijze taaktoewijzing.
Literature survey, Report 93.3.LT.4176, Transport Technology, Logistic Engineering.


This report investigates methods to assign couples of jobs to servers.

Couples assignment is a special case of the classic assignment problem, dedicated to problems where:
  1. short jobs arise frequently;
  2. different stages in the jobs can be distinguished, or
    the jobs can be split in two groups;
  3. resettimes are sequence dependant.
Couples assignment is first modelled as a 0,1-problem, minimising the total costs of the assignment and subjected to the following restrictions:
  1. Each server is used exactly once in the first assignment;
  2. Each job is done exactly once after both assignments;
  3. If a job is assigned in the first round it must have exactly one successor;
  4. If a job is not assigned in the first round it must have no successors.
In order to use efficient linear programming techniques this 0,1-problem is transformed to a minimum cost flow problem, which garantees an integer solution when integer data are used. Therefor restriction 2 is replaced by the following two:
  1. Every job is done at most once in the first assignment;
  2. Every job is done at most once in the second assignment.
Replacing restriction 2 by restriction 2a and 2b creates the possibility of assigning a certain job twice. The following three techniques can be used to solve this problem:
  1. Branch-and-bound techniques: The job assigned twice is forced in the first assignment or in the second assignment. Then a bound can be found using the e-Relaxation Algorithm.
  2. Using price-rises: The double assigned job is made less "favourable" by a rising its prices, after which the e-Relaxation Algorithm can be used again.
  3. The minimum cost flow problem is abandoned by adding a restriction which explicitly forbids to assign a job twice.

Reports on Logistic Engineering (in Dutch)
Modified: 2000.12.08; logistics@3mE.tudelft.nl , TU Delft / 3mE / TT / LT.