Seite - 117 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 50 Theconstraints abovedonot take into consideration thecompetitionofoperations that try to allocatethesameresource.Wecandistinguishtwotypesofcompetitionhere: competitionofoperations withinoneorderandcompetitionofoperationsofdifferentorders. Thecompetitionofoperationson parallel branchesofoneorder is consideredseparatelybymodelling the schedulingproblemfora singleorder (this isoutof thescopeof thispaper). Themainscopeof this research is toaddress the competitionofoperations fromdifferentorders.Assumingwehavetherule (constraint) thatconsiders thecompetitionofoperationswithinoneandthesameorder letus formalize thecompetitionbetween theoperationsofdifferentorders.Considerwehavearesource,which isbeingallocatedbyKdifferent operationsof |F|differentorders. Foreachresource r= 1,. . . , |R| letusdistinguishonly thoseoperations thatallocate itduring their run. Thesetof suchoperations canbe found fromthecorrespondingcolumnof the resource allocationmatrixOp=< opir>, i=1,. . . , |J|, r=1,. . . , |R|. xr= x|colr(Op)=1. Theexample for twocompetingoperationsof twodifferentorders is showninFigure1. Figure1.Competingoperationsononeresource. For each resource r= 1,. . . , |R| each competingoperation i= index(xr) = 1,. . . ,K of order f=1,. . . , |F|will competewithallothercompetingoperationsofallotherorders, i.e.,goingbackto theexampledepicted inFigure1wewillhave the followingconstraint foreachpairofoperations: xiϕ≥ xjψ+τj XORxjψ≥ xiϕ+τi, where indexesareas follows i, j= 1,. . . ,K; ϕ,ψ= 1,. . . , |F|; ϕ =ψ. Implementinganadditional Booleanvariable ck∈{0,1}will converteachpairofconstraints intoonesingle formula: ck ·xi,ϕ+(1−ck) ·xjψ≥ ck ·(xjψ+τj)+(1−ck) ·(xiϕ+τi). From the above precedence constraints, we can form the following set of constraints for the optimizationproblem: gi,j ·xi,f ≥ xi,f+τi, f=1,. . . , |F|, i=1,. . . , |J|, j=1,. . . , |J|, (1) x|J|f+τ|J| ≤ df , f=1,. . . , |F|, (2) ck ·xi,ϕ+(1−ck) ·xjψ≥ ck ·(xjψ+τj)+(1−ck) ·(xiϕ+τi), ϕ,ψ=1,. . . , |F|, ϕ =ψ, (3) xif>0, f=1,. . . , |F|, ck∈{0,1}, k=1,. . . ,K. 117