F.C. van Lookeren Campagne
Methoden voor paarsgewijze taaktoewijzing.
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:
Couples assignment is first modelled as a 0,1-problem, minimising the total
costs of the assignment and subjected to the following restrictions:
- short jobs arise frequently;
- different stages in the jobs can be distinguished, or
the jobs can be split in two groups;
- resettimes are sequence dependant.
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
- Each server is used exactly once in the first assignment;
- Each job is done exactly once after both assignments;
- If a job is assigned in the first round it must have exactly one successor;
- If a job is not assigned in the first round it must have no successors.
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:
- Every job is done at most once in the first assignment;
- Every job is done at most once in the second assignment.
- 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
- 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.
- 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)
, TU Delft