producer_consumer
Purpose
A Producer Consumer Scheduling constraint. More formally the constraint ensures that:
productionsj · durationsj = prodsizesj for all j in Tasks
consumptionsj · durationsj = consosizesj for all j in Tasks
∑j ∈ R | t ∈ [UB(startj)..LB(endj)] (productionsj - consumptionsj) ≤ Ct for all t in Times
Synopsis
function producer_consumer(starts:array(range) of cpvar, ends:array(range) of cpvar, durations:array(range) of cpvar, productions:array(range) of cpvar, prod_sizes:array(range) of cpvar, consumptions:array(range) of cpvar, conso_sizes:array(range) of cpvar, C:array(range) of integer) : cpctr
Arguments
|
starts
|
array of starting times
|
|
ends
|
array of ending times
|
|
durations
|
array of durations
|
|
productions
|
array of tasks' requirements
|
|
prod_sizes
|
array of tasks' productions
|
|
consumptions
|
array of tasks' provisions
|
|
conso_sizes
|
array of tasks' consumptions
|
|
C
|
initial resource capacity array indexed by time
|
Example
The following example shows how to use the producer_consumer constraint for the problem of planning the construction of a house (an example of resource-constrained project scheduling).
model "Cumulative Scheduling"
uses "kalis"
setparam("KALIS_DEFAULT_LB",0)
setparam("KALIS_DEFAULT_UB",100)
declarations
! Task indices
Masonry = 1; Carpentry= 2; Roofing = 3; Windows = 4
Facade = 5; Garden = 6; Plumbing = 7; Ceiling = 8
Painting= 9; MovingIn =10; InitialPayment=11; SecondPayment=12
BUILDTASKS = 1..10
PAYMENTS = 11..12
TASKS = BUILDTASKS+PAYMENTS
TNAMES: array(TASKS) of string
obj:cpvar ! Objective variable
starts : array(TASKS) of cpvar ! Start times variables
ends : array(TASKS) of cpvar ! Completion times
durations: array(TASKS) of cpvar ! Durations of tasks
consos : dynamic array(TASKS) of cpvar ! Res. consumptions
sizes : dynamic array(TASKS) of cpvar ! Consumption sizes
prods : dynamic array(TASKS) of cpvar ! Res. production
sizep : dynamic array(TASKS) of cpvar ! Production sizes
Strategy : cpbranching ! Branching strategy
end-declarations
TNAMES:: (1..12)["Masonry", "Carpentry", "Roofing", "Windows",
"Facade", "Garden", "Plumbing", "Ceiling", "Painting",
"MovingIn", "InitialPayment", "SecondPayment"]
! Setting the names of the variables
forall(j in TASKS) do
starts(j).name := TNAMES(j)+".start"
ends(j).name := TNAMES(j)+".end"
durations(j).name := TNAMES(j)+".duration"
end-do
! Creating consumption variables
forall(j in BUILDTASKS) do
create(sizes(j))
sizes(j).name := TNAMES(j)+".size"
create(consos(j))
consos(j).name := TNAMES(j)+".conso"
end-do
! Setting durations of building tasks
durations(Masonry) =7; durations(Carpentry)=3; durations(Roofing) =1
durations(Windows) =1; durations(Facade) =2; durations(Garden) =1
durations(Plumbing)=8; durations(Ceiling) =3; durations(Painting)=2
durations(MovingIn)=1
! Precedence constraints among building tasks
starts(Carpentry) >= ends(Masonry)
starts(Roofing) >= ends(Carpentry)
starts(Windows) >= ends(Roofing)
starts(Facade) >= ends(Roofing)
starts(Garden) >= ends(Roofing)
starts(Plumbing) >= ends(Masonry)
starts(Ceiling) >= ends(Masonry)
starts(Painting) >= ends(Ceiling)
starts(MovingIn) >= ends(Windows)
starts(MovingIn) >= ends(Facade)
starts(MovingIn) >= ends(Garden)
starts(MovingIn) >= ends(Painting)
! Setting task consumptions
consos(Masonry) = 7; consos(Carpentry) = 3; consos(Roofing) = 1
consos(Windows) = 1; consos(Facade) = 2; consos(Garden) = 1
consos(Plumbing) = 8; consos(Ceiling) = 3; consos(Painting) = 2
consos(MovingIn) = 1
! Production (amount) of payment tasks
forall(j in PAYMENTS) do
create(prods(j))
prods(j).name := TNAMES(j)+".prod"
create(sizep(j))
sizep(j).name := TNAMES(j)+".sizep"
end-do
! Payment data
prods(InitialPayment) = 20; prods(SecondPayment) = 9
durations(InitialPayment) = 1; durations(SecondPayment) = 1
starts(InitialPayment) = 0; starts(SecondPayment) = 15
! Objective: makespan of the schedule
obj = maximum({ ends(Masonry) , ends(Carpentry), ends(Roofing),
ends(Windows), ends(Facade), ends(Garden), ends(Plumbing),
ends(Ceiling), ends(Painting), ends(MovingIn)})
! Posting the producer_consumer constraint
producer_consumer(starts,ends,durations,prods,sizep,consos,sizes)
! Setting the search strategy
Strategy:= assign_var(KALIS_SMALLEST_MIN, KALIS_MIN_TO_MAX, starts)
cp_set_branching(Strategy)
! Find the optimal solution
if cp_minimize(obj) then
writeln("Minimum makespan: ", obj.sol)
forall(j in BUILDTASKS)
writeln(TNAMES(j), ": ", starts(j).sol, " - ", ends(j).sol)
else
writeln("No solution found")
end-if
end-model
Related topics
© 2001-2024 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.