| |||||||||

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 ! One receiver per transmitter forall(t in TRANSM) onerec(t):= sum(r in RECV | TQBS(t,r)>0) flow(t,r) =1 ! One transmitter per receiver 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 svgaddgroup(TGraph(t), "Receiver "+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 svgaddpoint(TGraph(round(solflowr(t,m))), ct+i, t*FACT) 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 | |||||||||

Copyright 2017 Fair Isaac Corporation. |