| |||||||||
| |||||||||
Hybrid MIP-CP problem solving: concurrent solving Description The problem of scheduling a given set of jobs on a set of
machines where durations and cost depend on the choice of
the resource may be broken down into several subproblems,
machine assignment and single-machine sequencing.
The main problem (machine assignment)
is solved as a MIP problem and the sequencing
subproblems solved at the nodes of the branch-and-bound
search generate new constraints that are added to the
main problem using the cut manager functionality of
Xpress Optimizer. Several implementations of this
decomposition approach are available, either using a
hybrid MIP-CP formulation or a second MIP model for
solving the subproblems. The solving of the subproblems
may be executed sequentially or in parallel.
Source Files By clicking on a file name, a preview is opened at the bottom of this page. Data Files sched_submpd.mos
(!****************************************************************
Mosel example problems
======================
file sched_submpd.mos
`````````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
-- Parallel solving of sequencing subproblems --
-- Distributed computing version --
MIP branch-and-cut problem solving: cut generation for MIP model
by solving MIP subproblems at nodes in the MIP branching tree.
*** Not intended to be run standalone - run from sched_mainmpd.mos ***
(c) 2010 Fair Isaac Corporation
author: S. Heipcke, May 2010
*****************************************************************!)
model "Schedule (MIP+MIP) MIP subproblem"
uses "mmxprs", "mmjobs" , "mmsystem"
parameters
DATAFILE = "sched_3_12.dat"
VERBOSE = 1
M = 1 ! Number of the machine
NP = 12 ! Number of products
MODE = 1 ! 1 - decide feasibility
! 2 - return complete solution
end-parameters
startsolve:= gettime
declarations
PRODS = 1..NP ! Set of products
ProdMach: set of integer
end-declarations
initializations from "rmt:sol_"+M+".dat"
ProdMach
end-initializations
finalize(ProdMach)
NJ:= getsize(ProdMach)
declarations
RANKS=1..NJ ! Task positions
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
DURm: array(ProdMach) of integer ! Processing times on machine m
solstart: array(ProdMach) of integer ! Solution values for start times
rank: array(ProdMach,RANKS) of mpvar ! =1 if task p at position k
start: array(RANKS) of mpvar ! Start time of task at position k
comp: array(RANKS) of mpvar ! Completion time of task at pos. k
finish: mpvar ! Total completion time
EVENT_SOLVED=2 ! Event codes sent by submodels
EVENT_FAILED=3
solvetime: real
end-declarations
initializations from "rmt:sol_"+M+".dat"
DURm
end-initializations
initializations from "rmt:"+DATAFILE
REL DUE
end-initializations
! One task per position
forall(k in RANKS) sum(p in ProdMach) rank(p,k) = 1
! One position per job
forall(p in ProdMach) sum(k in RANKS) rank(p,k) = 1
! Sequence of jobs
forall(k in 1..NJ-1)
start(k+1) >= start(k) + sum(p in ProdMach) DURm(p)*rank(p,k)
! Start times
forall(k in RANKS) start(k) >= sum(p in ProdMach) REL(p)*rank(p,k)
! Completion times
forall(k in RANKS) comp(k) = start(k) + sum(p in ProdMach) DURm(p)*rank(p,k)
! Due dates
forall(k in RANKS) comp(k) <= sum(p in ProdMach) DUE(p)*rank(p,k)
forall(p in ProdMach,k in RANKS) rank(p,k) is_binary
! Objective function: minimize latest completion time
forall(k in RANKS) finish >= comp(k)
! if MODE=1 then
setparam("XPRS_MAXMIPSOL", 1) ! Stop at first feasible solution
! end-if
minimize(finish)
res:= getparam("XPRS_MIPSTATUS")
! Pass solution to main problem
if (res=XPRS_MIP_SOLUTION or res=XPRS_MIP_OPTIMAL) then
forall(p in ProdMach)
solstart(p):=
round(getsol(start( round(getsol(sum(k in RANKS) k*rank(p,k))) )))
if MODE=2 then
initializations to "rmt:sol_"+M+".dat"
solstart as "sol"
end-initializations
end-if
send(EVENT_SOLVED,0)
else
send(EVENT_FAILED,0)
end-if
! Update total running time measurement
initializations from "rmt:time_"+M+".dat"
solvetime
end-initializations
solvetime+= gettime-startsolve
initializations to "rmt:time_"+M+".dat"
solvetime
end-initializations
end-model
| |||||||||
| © Copyright 2023 Fair Isaac Corporation. |
