disjunctive
disjunctive |
Purpose
This constraint states that the given tasks are not overlapping chronologically.
Synopsis
procedure disjunctive(starts: set of cpvar, durations:array(cpvar) of integer, disj:set of cpctr, resource:integer)
procedure disjunctive(starts: array(integer) of cpvar, durations:array(integer) of cpvar, ends: array(integer) of cpvar)
Arguments
|
starts
|
Array of variables representing the start times of the tasks
|
|
durations
|
Array of integers representing the durations of the tasks
|
|
ends
|
Array of variables representing the completion times of the tasks
|
|
disj
|
Empty array that will be filled with the list of disjunctions that will be created by this constraint
|
|
resource
|
Resource flag (argument currently unused)
|
Return value
A disjunctive constraint ensuring that the tasks defined by 'starts' and 'durations' are not overlapping chronologically.
Example
The following example shows how to use the disjunctive constraint to express resource constraints in a small disjunctive scheduling problem:
model "Disjunctive scheduling with settle_disjunction"
uses "kalis"
declarations
NBTASKS = 5
TASKS = 1..NBTASKS ! Set of tasks
DUR: array(TASKS) of integer ! Task durations
DURs: array(set of cpvar) of integer ! 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")
! Setting up the decision variables
forall (t in TASKS) do
start(t) >= 0
setname(start(t), "Start("+t+")")
DURs(start(t)):= DUR(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
disjunctive(union(t in TASKS) {start(t)}, DURs, Disj, 1)
! Define the search strategy
Strategy(1):= settle_disjunction
Strategy(2):= split_domain(KALIS_LARGEST_MIN,KALIS_MIN_TO_MAX)
cp_set_branching(Strategy)
setparam("KALIS_DICHOTOMIC_OBJ_SEARCH",true)
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