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.