Distributed policy search reinforcement learning for job-shop scheduling tasks
Authors:
- 13 June 2011
- journal article
- research article
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 50 (1) , 41-61
Abstract
We interpret job-shop scheduling problems as sequential decision problems that are handled by independent learning agents. These agents act completely decoupled from one another and employ probabilistic dispatching policies for which we propose a compact representation using a small set of real-valued parameters. During ongoing learning, the agents adapt these parameters using policy gradient reinforcement learning, with the aim of improving the performance of the joint policy measured in terms of a standard scheduling objective function. Moreover, we suggest a lightweight communication mechanism that enhances the agents' capabilities beyond purely reactive job dispatching. We evaluate the effectiveness of our learning approach using various deterministic as well as stochastic job-shop scheduling benchmark problems, demonstrating that the utilisation of policy gradient methods can be effective and beneficial for scheduling problems.Keywords
This publication has 16 references indexed in Scilit:
- RSPSA: Enhanced Parameter Optimization in Games2006
- Comparison of distributed methods for resource allocationInternational Journal of Production Research, 2005
- Natural Actor-Critic2005
- Adopt: asynchronous distributed constraint optimization with quality guaranteesArtificial Intelligence, 2005
- The Complexity of Decentralized Control of Markov Decision ProcessesMathematics of Operations Research, 2002
- Global supply chain management: A reinforcement learning approachInternational Journal of Production Research, 2002
- A survey of factory control algorithms that can be implemented in a multi-agent heterarchy: Dispatching, scheduling, and pullJournal of Manufacturing Systems, 1998
- Simple statistical gradient-following algorithms for connectionist reinforcement learningMachine Learning, 1992
- OR-Library: Distributing Test Problems by Electronic MailJournal of the Operational Research Society, 1990
- Filtered beam search in scheduling†International Journal of Production Research, 1988