settle_disjunction
settle_disjunction |
Purpose
Creates a settle_disjunction branching scheme that resolves the status of all the disjunctions passed in argument. The branching consists in choosing one branch of the disjunction and posting the constraint stated by this branch. The branches are tested from left to right
Synopsis
function settle_disjunction(constraints:set of cpctr) : cpbranching
function settle_disjunction(constraints:array(range) of cpctr) : cpbranching
function settle_disjunction : cpbranching
Argument
|
constraints
|
the disjunctions
|
Return value
The resulting settle_disjunction branching scheme
Example
The following example shows how to use the settle_disjunction branching scheme to solve a small disjunctive scheduling problem: The problem is to find a schedule for a set of tasks on one machine. The machine can process only one task at the time and the goal is to minimize the total weighted tardiness of the schedule.
model "Disjunctive scheduling with settle_disjunction"
uses "kalis"
declarations
NBTASKS = 5
TASKS = 1..NBTASKS ! Set of tasks
DUR: array(TASKS) of integer ! Task durations
DUE: array(TASKS) of integer ! Due dates
WEIGHT: array(TASKS) of integer ! Weights of tasks
start: array(TASKS) of cpvar ! Start times
tmp: array(TASKS) of cpvar ! Aux. variable
tardiness: array(TASKS) of cpvar ! Tardiness
twt: cpvar ! Objective variable
zeroVar: cpvar ! 0-valued variable
Strategy: array(range) of cpbranching ! Branching strategy
Disj: set of cpctr ! Disjunctions
end-declarations
DUR :: [21,53,95,55,34]
DUE :: [66,101,232,125,150]
WEIGHT :: [1,1,1,1,1]
setname(twt, "Total weighted tardiness")
zeroVar = 0
setname(zeroVar, "zeroVar")
forall (t in TASKS) do
start(t) >= 0
setname(start(t), "Start("+t+")")
tmp(t) = start(t) + DUR(t) - DUE(t)
setname(tardiness(t), "Tard("+t+")")
tardiness(t) = maximum({tmp(t),zeroVar})
end-do
twt = sum(t in TASKS) (WEIGHT(t) * tardiness(t))
! Create the disjunctive constraints
forall(t in 1..NBTASKS-1, s in t+1..NBTASKS)
(start(t) + DUR(t) <= start(s)) or
(start(s) + DUR(s) <= start(t))
! Define the branching strategy
Strategy(1):= settle_disjunction
Strategy(2):= split_domain(KALIS_LARGEST_MIN,KALIS_MIN_TO_MAX)
cp_set_branching(Strategy)
! Solve the problem
if not(cp_minimize(twt)) then
writeln("Problem is inconsistent")
exit(0)
end-if
forall (t in TASKS)
writeln("[", getsol(start(t)), "==>",
getsol(start(t)) + DUR(t), "]:\t ",
getsol(tardiness(t)), " (", getsol(tmp(t)), ")")
writeln("Total weighted tardiness: ", getsol(twt))
end-model
Related topics