Throughput maximization of capacitated re-entrant lines through fluid relaxation
Michael Ibrahim, Spyros A. Reveliotis · 2018
This paper extends the scheduling methodology for complex stochastic networks that is based on the solution of a “fluid” relaxation at each decision point of the original scheduling problem, to stochastic networks with blocking and deadlocking effects. For a clearer and more concrete treatment, the presented results are developed in the operational context of a re-entrant line with finite buffering capacity at each workstation; these re-entrant lines are characterized as “capacitated re-entrant lines (CRLs)”. From a methodological standpoint, the paper results are enabled by a pre-established ability to control the underlying resource allocation for deadlock freedom, and by the further ability to express the corresponding deadlock avoidance policy as a set of linear inequalities on the system state. Also, the employed LP relaxation differs considerably from similar past developments, since it must account for the blocking effects that take place in the considered CRLs. A small example provided at the last part of the paper highlights all the aforementioned developments, and helps assessing their efficacy.