Multi Machine Scheduling: An Agent-Based Approach

Abstract

Scheduling of multiple parallel machines in the face of sequence dependent setups and downstream considerations is a hard problem. No single efficient algorithm is guaranteed to produce optimal results. We describe a solution for an instance of this problem, in the domain of paper manufacturing. The problem has additional job machine restrictions and fixed costs of assigning jobs to machines. We consider multiple objectives such as minimizing (weighted) tardiness, minimizing job-machine assignment costs. We solve the problem using a simple agent architecture called the Asynchronous team (A-team), in which agents cooperate by exchanging results. We have built agents each of which encapsulates a different problem solving strategy for solving the multi-machine scheduling problem. The A-team framework enables the agents to cooperate to produce better results than those of any individual agent. In this paper we define the problem, describe the individual agents, and show with experimental results that the A-team produces very good results compared to schedulers alone.