 FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home   Open shop scheduling

Description
A satellite routes the traffic from four transmitter stations to four receiver stations. It has a switch that allows any permutation (mode) between the four transmitters and the four receivers. A valid schedule of transmissions defines a sequence of permutations that routes all the traffic of the given traffic matrix TRAF. An element of TRAF may be fragmented, and appear in several modes of the final decomposition. The objective is to find a schedule with minimal total duration. The solution algorithm solves an assignment problem for every permutation.

Further explanation of this example: 'Applications of optimization with Xpress-MP', Section 12.5 'Scheduling of telecommunications via satellite'

Source Files

Data Files

openshop_graph.mos

```(!******************************************************
Mosel Example Problems
======================

file openshop.mos
`````````````````
TYPE:         Preemptive open shop scheduling
DIFFICULTY:   5
FEATURES:     MIP problem, data preprocessing, algorithm for preemptive
scheduling that involves looping over optimization,
`Gantt chart' printing and drawing
DESCRIPTION:  A satellite routes the traffic from four transmitter
stations to four receiver stations. It has a switch that
allows any permutation (mode) between the four transmitters
and the four receivers. A valid schedule of transmissions
defines a sequence of permutations that routes all the
traffic of the given traffic matrix TRAF. An element of
TRAF may be fragmented, and appear in several modes of
the final decomposition. The objective is to find a
schedule with minimal total duration.
The solution algorithm solves an assignment problem for
every permutation.
FURTHER INFO: `Applications of optimization with Xpress-MP',
Section 12.5 `Scheduling of telecommunications via satellite'

(c) 2008 Fair Isaac Corporation
author: S. Heipcke, 2002, rev. Sep. 2017
*******************************************************!)

model "Satellite scheduling"
uses "mmxprs", "mmsvg"

declarations
TRANSM = 1..4                         ! Set of transmitters
RECV = 1..4                           ! Set of receivers

TRAF: array(TRANSM,RECV) of integer   ! Traffic betw. terrestrial stations
TQBS: array(TRANSM,RECV) of integer   ! Quasi bistochastic traffic matrix
row: array(TRANSM) of integer         ! Row sums
col: array(RECV) of integer           ! Column sums
LB: integer                           ! Maximum of row and column sums
end-declarations

initializations from 'openshop.dat'
TRAF
end-initializations

! Row and column sums
forall(t in TRANSM) row(t):= sum(r in RECV) TRAF(t,r)
forall(r in RECV) col(r):= sum(t in TRANSM) TRAF(t,r)
LB:=maxlist(max(r in RECV) col(r), max(t in TRANSM) row(t))

! Calculate TQBS
forall(t in TRANSM,r in RECV) do
q:= minlist(LB-row(t),LB-col(r))
TQBS(t,r):= TRAF(t,r)+q
row(t)+=q
col(r)+=q
end-do

declarations
MODES: range

flow: array(TRANSM,RECV) of mpvar         ! 1 if transmission from t to r,
! 0 otherwise
pmin: mpvar                               ! Minimum exchange
onerec, minexchg: array(TRANSM) of linctr ! Constraints on transmitters
! and min exchange
onetrans: array(RECV) of linctr           ! Constraints on receivers

solflowt: array(TRANSM,MODES) of integer  ! Solutions of every iteration
solflowr: array(RECV,MODES) of integer    ! Solutions of every iteration
solpmin: array(MODES) of integer          ! Objective value per iteration
end-declarations

forall(t in TRANSM,r in RECV) flow(t,r) is_binary

ct:= 0
while(sum(t in TRANSM,r in RECV) TQBS(t,r) > 0) do
ct+=1

forall(t in TRANSM) onerec(t):= sum(r in RECV | TQBS(t,r)>0) flow(t,r) =1
forall(r in RECV) onetrans(r):= sum(t in TRANSM | TQBS(t,r)>0) flow(t,r) =1

! Minimum exchange
forall(t in TRANSM)
minexchg(t):= sum(r in RECV | TQBS(t,r)>0) TQBS(t,r)*flow(t,r) >= pmin

! Solve the problem: maximize the minimum exchange
maximize(pmin)

! Solution printing
writeln("Round ", ct, " objective: ", getobjval)

! Save the solution
solpmin(ct):= round(getobjval)
forall(t in TRANSM,r in RECV | TQBS(t,r)>0)
if(getsol(flow(t,r))>0) then
solflowt(t,ct):= t
solflowr(t,ct):= r
end-if

! Update TQBS
forall(t in TRANSM)
TQBS(solflowt(t,ct),solflowr(t,ct)) -= solpmin(ct)

end-do

! Solution printing
writeln("\nTotal duration: ", sum(m in MODES) solpmin(m))

write("      ")
forall(i in 0..ceil(LB/5)) write(strfmt(i*5,5))
writeln
forall(t in TRANSM) do
write("From ", t, " to: ")
forall(m in MODES)
forall(i in 1..solpmin(m)) do
write(if(TRAF(solflowt(t,m),solflowr(t,m))>0, string(solflowr(t,m)),"-"))
TRAF(solflowt(t,m),solflowr(t,m))-=1
end-do
writeln
end-do

! Solution drawing
declarations
TGraph: array(RECV) of string
end-declarations

initializations from 'openshop.dat'
TRAF
end-initializations

FACT:=3
svgsetgraphviewbox(1, 0, sum(m in MODES) solpmin(m)+1, FACT*TRANSM.size+1)
svgsetgraphscale(FACT)
svgsetgraphpointsize(FACT)
svgsetgraphlabels("Time", "Transmitters")

forall(t in TRANSM) do
TGraph(t):="R"+t
end-do
forall(t in TRANSM) do
ct:=0
forall(m in MODES) do
forall(i in 1..solpmin(m)) do
if(TRAF(solflowt(t,m),solflowr(t,m))>0) then
end-if
TRAF(solflowt(t,m),solflowr(t,m))-=1
end-do
ct+=solpmin(m)
end-do
end-do

svgsave("openshop.svg")
svgrefresh
svgwaitclose("Close browser window to terminate model execution.", 1)
end-model

```   