Randomized Lagrangian heuristic based on Nash equilibrium for large scale single machine scheduling problem
- Resource Type
- Conference
- Authors
- Gu, Hanyu; Xi, Yugeng; Tao, Jiping
- Source
- 2007 IEEE 22nd International Symposium on Intelligent Control Intelligent Control, 2007. ISIC 2007. IEEE 22nd International Symposium on. :464-468 Oct, 2007
- Subject
- Robotics and Control Systems
Computing and Processing
Lagrangian functions
Nash equilibrium
Large-scale systems
Single machine scheduling
Job shop scheduling
Relaxation methods
Processor scheduling
Linear programming
Automation
Approximation algorithms
- Language
- ISSN
- 2158-9860
2158-9879
Lagrangian relaxation method for jobshop scheduling problems has been studied in the framework of combinatorial auction. In this paper a noncooperative game model is built for the Lagrangian relaxation method, and we prove that the equivalent continuous relaxation computed from the Lagrangian dual problem provides a mixed strategy Nash equilibrium for this game model. Based on this interpretation a randomized heuristic is exploited to get feasible schedules. Numerical experiments are carried out on a large scale single machine problem.