TY - JOUR

T1 - Q-learning algorithm performance for m-machine, n-jobs flow shop scheduling problems to minimize makespan

AU - Fonseca-Reyna, Yunior César

AU - Martínez-Jiménez, Yailen

AU - Nowé, Ann

PY - 2017/1/1

Y1 - 2017/1/1

N2 - Flow Shop Scheduling Problems circumscribes an important class of sequencing problems in the field of production planning. The problem considered here is to find a permutation of jobs to be sequentially processed on a number of machines under the restriction that the processing of each job has to be continuous with respect to the objective of minimizing the completion time of all jobs, known in literature as makespan or Cmax. This problem is as NP-hard, it is typical of combinatorial optimization and can be found in manufacturing environments, where there are conventional machines-tools and different types of pieces which share the same route. The following research presents a Reinforcement Learning algorithm known as Q-Learning to solve problems of the Flow Shop category. This algorithm is based on learning an action-value function that gives the expected utility of taking a given action in a given state where an agent is associated to each of the resources. To validate the quality of the solutions, test cases of the specialized literature are used and the results obtained are compared with the reported optimal results.

AB - Flow Shop Scheduling Problems circumscribes an important class of sequencing problems in the field of production planning. The problem considered here is to find a permutation of jobs to be sequentially processed on a number of machines under the restriction that the processing of each job has to be continuous with respect to the objective of minimizing the completion time of all jobs, known in literature as makespan or Cmax. This problem is as NP-hard, it is typical of combinatorial optimization and can be found in manufacturing environments, where there are conventional machines-tools and different types of pieces which share the same route. The following research presents a Reinforcement Learning algorithm known as Q-Learning to solve problems of the Flow Shop category. This algorithm is based on learning an action-value function that gives the expected utility of taking a given action in a given state where an agent is associated to each of the resources. To validate the quality of the solutions, test cases of the specialized literature are used and the results obtained are compared with the reported optimal results.

KW - Flow-shop

KW - Makespan

KW - Optimization

KW - Q-learning

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=85019621318&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85019621318

VL - 38

SP - 281

EP - 290

JO - Investigacion Operacional

JF - Investigacion Operacional

SN - 0257-4306

IS - 3

ER -