Actor-critic deep reinforcement learning for solving job shop scheduling problems

Chien Liang Liu*, Chuan Chin Chang, Chun Jan Tseng

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

In the past decades, many optimization methods have been devised and applied to job shop scheduling problem (JSSP) to find the optimal solution. Many methods assumed that the scheduling results were applied to static environments, but the whole environments in the real world are always dynamic. Moreover, many unexpected events such as machine breakdowns and material problems may be present to adversely affect the initial job scheduling. This work views JSSP as a sequential decision making problem and proposes to use deep reinforcement learning to cope with this problem. The combination of deep learning and reinforcement learning avoids handcraft features as used in traditional reinforcement learning, and it is expected that the combination will make the whole learning phase more efficient. Our proposed model comprises actor network and critic network, both including convolution layers and fully connected layer. Actor network agent learns how to behave in different situations, while critic network helps agent evaluate the value of statement then return to actor network. This work proposes a parallel training method, combining asynchronous update as well as deep deterministic policy gradient (DDPG), to train the model. The whole network is trained with parallel training on a multi-agent environment and different simple dispatching rules are considered as actions. We evaluate our proposed model on more than ten instances that are present in a famous benchmark problem library - OR library. The evaluation results indicate that our method is comparative in static JSSP benchmark problems, and achieves a good balance between makespan and execution time in dynamic environments. Scheduling score of our method is 91.12% in static JSSP benchmark problems, and 80.78% in dynamic environments.

Original languageEnglish
Article number9066984
Pages (from-to)71752-71762
Number of pages11
JournalIEEE Access
Volume8
DOIs
StatePublished - 2020

Keywords

  • actor-critic network
  • deep reinforcement learning
  • Job shop scheduling problem (JSSP)
  • parallel training

Fingerprint Dive into the research topics of 'Actor-critic deep reinforcement learning for solving job shop scheduling problems'. Together they form a unique fingerprint.

Cite this