《2016 Improving the Lagrangian Relaxation Approach for Large Job-shop Scheduling》.pdf

Proceedingsof the 39’ IEEE Conference onDecision and Control Sydney,Australia December,2000 Improving the Lagrangian Relaxation Approach for Large Job-shop Scheduling Lei Fang, Peter B.Luh, Haoxun Chen Department of Electrical SystemsEngineering University of Connecticut Stons, CT 06269-2157 fang@engr.uconn.edu, luh@engr.uconn.edu, hxchen@enrrr.uconn.edu Abstract. Lagrangian Relaxation (LR) has recently However, the SG ([7], [8]) becomes inefficient for large emerged as a practical approach for job shop scheduling problems with thousands of subproblems, since it requires problems of realistic size. The efficiency of the approach, minimizing all the subproblems to obtain a search however, depends on how fast the dual problem is solved direction. For problems of large sizes, the surrogate and how good the feasible solutions are constructed. The subgradient method (SSG) was recently developed, where purpose of this paper is to address above two issues. First, only approximate optimization of the Lagrangian dual is a “variable target value” method is used to regulate the needed to obtain a proper “surrogate subgradient direction” step size for surrogate subgradient optimization. The [91. target values are updated iteratively whenever necessary, As far as related step size rules are concerned, they depending on the information obtained in the process of play an important role in governing the practical rate of t