Game theoretic Multi-agent algorithms for the job shop scheduling problem
Abstract
Job shop scheduling problem is a problem of scheduling n jobs on m machines with each job
having a set of equal number of operation that are to be process in unique machine routes.
The Job Shop Scheduling (JSSP) is one of the hardest combinatorial optimization problems
and has been researched over the decade. This study proposes a new approach to solve a
Job Shop Scheduling problem by structuring the problem as multi-agent system (MAS) and
using 3 game theoretic algorithms to achieve the scheduling objectives. The objective of this
study is to minimize the makespan. This approach is meant to achieve feasible schedules
within reasonable time across different problem instances. This research solves the
scheduling of operation on different machine and defines the sequence of operation
processing on the respective machine. Job Scheduling problem is a resource allocation
problem is mainly apparent in manufacturing environment, in which the jobs are allocated to
various machines. Jobs are the activities and a machine represents the resources. It is also
common in transportation, services and grid scheduling. The result and performance of the
proposed algorithms are compared against other conventional algorithms. The comparison is
on benchmark data used across multiple studies on JSSP.