Seite - 116 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 50 Fromtheconceptualpointofview, thispaperdealswithamixed integernon-linear (MINLP) schedulingproblem[5]that isrelaxedtoacombinatorialsetof linearprogrammingproblemsduetothe linear“makespan”objective function.Asabasicapproachwetakethedisjunctivemodel [4].Asimilar approachwasdemonstrated in [7]where the authors deployed the concept of parallel dedicated machines scheduling subject to precedence constraints and implemented aheuristic algorithm to generateasolution. 2.MaterialsandMethods Inorder to formalize thecontinuous-timeschedulingproblemwewillneedto introduceseveral basicdefinitionsandvariables.After that,wewill formasystemofconstraints that reflectdifferent physical, logical and economic restrictions that are in place for real industrial processes. Finally, introducingtheobjective functionwillfinishtheformulationofRCPSPasanoptimizationproblem suitable forsolving. 2.1.NotionsandBaseData forScheduling Stickingto the industrial schedulingalsoknownas the JobShopproblem, letusdefinethemain notions thatwewilluse in the formulation: • Theenterprise functioningprocessutilizes resourcesofdifferent types (for instancemachines, personnel, riggings, etc.). The set of the resources is indicated by a variable R = {Rr}, r=1,. . . , |R|. • Themanufacturingprocedureof theenterprise is formalizedasasetofoperations J tiedwith eachotherviaprecedencerelations. Precedencerelationsarebrought toamatrixG=< gij>, i= 1,. . . , |J|, j= 1,. . . , |J|. Eachelementof thematrix gij = 1 iff theoperation j follows the operation iandzerootherwisegij=0. • Eachoperation i isdescribedbydurationτi. Elementsτi, i=1,. . . , |J|, formavectorofoperations’ durations−→τ. • Each operation i has a list of resources it uses while running. Necessity for resources for each operation is represented by thematrixOp =< opir >, i = 1,. . . , |J|, r = 1,. . . , |R|. Eachelementof thematrixopir=1 iff theoperation iof themanufacturingprocessallocates the resource r. Allothercasesbringtheelement tozerovalueopir=0. • The inputordersof theenterpriseareconsideredasmanufacturingtasks for thecertainamount ofendproductandareorganized intoasetF. Eachorder is characterizedby theendproduct amount vf and thedeadline df , f = 1,. . . , |F|. Elements inside F are sorted in thedeadline ascendingorder. Using thedefinitions introducedabove,wecannowformalize theschedulingprocessas residing all |J|operationsofall |F|ordersonthesetof resourcesR.Mathematically thismeansdefiningthe start timeofeachoperation i=1,. . . , |J|ofeachorder f=1,. . . , |F|. 2.2. Continuous-TimeProblemSetting Thecontinuous-timecase is formulatedaroundthevariables that standfor thestartmomentsof eachoperation iofeachorder f: xif ≥0, i=1,. . . , |J|, f=1,. . . , |F| [3]. Thevariablesxif ≥0can becombinedinto |F|vectors−→xf ≥0. Themainconstraintsof theoptimizationprobleminthatcaseare: • Precedencegraphof themanufacturingprocedure: G−→xf ≥ (−→xf +−→τ ), f=1,. . . , |F|. • Meetingdeadlines forallorders x|J|f+τ|J| ≤ df , f=1,. . . , |F|. 116