Distributed personnel scheduling – negotiation among scheduling agents

This paper introduces a model for Distributed Employee Timetabling Problems (DisETPs) and proposes a general architecture for solving DisETPs by using a Multi Agent System paradigm. The architecture is composed of a set of autonomous software Scheduling Agents (SAs) that solve the Employee Timetabling Problems (ETP) for each department. Each agent has its own local ETP problem and its own goals. The Scheduling Agents must coordinate their local solution with the other agents in order to achieve a global solution for the whole organization that yields a better result with respect to the organization's global targets. To achieve a coherent and consistent global solution, the SAs make use of a sophisticated negotiation protocol among scheduling agents that always ends in an agreement (not ensured to be optimal). The main functionalities of this protocol are agent to agent relation definition, a mechanism to approve a chain of Request for Changes and an electronic marketplace for bidding on preferred common time slots. Experimental analysis of the implemented Multi Agent System for the Soroka medical center is presented. The results of our study indicate that the proposed framework has the potential to reduce the cost of transportation for the nurses that traveling to and from the hospital.