《2016 Lagrangian relaxation for complex job shop scheduling》.pdf

Proceedings of the 2006 IEEE International Conference on Robotics and Automation Orlando, Florida - May 2006 Lagrangian Relaxation for Complex Job Shop Scheduling Tao Sun Peter B. Luh Min Liu Center for Intelligent and Networked Center for Intelligent and Networked Department of Automation, Systems, Department of Automation Systems, Department of Automation Tsinghua University, Beijing 100084, Tsinghua University, Beijing 100084, Tsinghua University, Beijing, China China China Department of Electrical and Computer liumin@cims.tsinghua.edu.cn suntao99@mails.tsinghua.edu.cn Engineering University of Connecticut, Storrs, USA Abstract – Market competition forces manufactures to schedule their resources efficiently for on-time order delivery and low inventory. However, for companies such as textile and steel-making companies, optimizing schedules is difficult because of the NP-hard nature of the problem and the complex product structures: assemblies, disassemblies and couplings across orders. To address the difficulties, this paper extends the Lagrangian relaxation approach through selectively relaxing precedence constraints. The solution oscillation is identified and alleviated by adding auxiliary penalty and by nonlinear approximation. Furthermore, the normalized surrogate Fig. 1 A two-order scheduling problem with complex structures. subgradient method is developed