Collective Approach Based on Pheromone Style Communication to Nurse Scheduling Problems

Masahito Yamamoto, Graduate School of Engineering, Hokkaido University, Japan
Email: masahito@complex.eng.hokudai.ac.jp

H. Kawamura, Graduate School of Engineering, Hokkaido University, Japan
Email: kawamura@complex.eng.hokudai.ac.jp

K. Suzuki, Graduate School of Engineering, Hokkaido University, Japan

A. Ohuchi, Graduate School of Engineering, Hokkaido University, Japan

In this paper, we present a collective approach, such as Ant System, in which many agents behave intelligently in complex environment. Particularlly, we forcus on a pheromone use in Ant System, and propose the framework of collective algorithm for solving simple Nurse Scheduleing Problems (NSPs). NSPs are well known to be very difficult combinatorial optimization problems, because a large number of constraints exist and thus one can't know even if there is a solution which satisfies all constraints.

In our algorithm, each agent senses a partial environment (generate a partial schedule) and tries to behave according to their own criterion autonomously (change their partial schedule). Generally, an entire schedule, obtained in this way, results in an infeasible solution (does not nessesary satisfy all constraints). Therefore, through communication among agents, they modify their partial scheudle and tries to dissolve conflicts. As a communication method, we adopt pheromone style communication, because they are very simple but effective. Pheromone are used in order to resolve conflicts among agents, i.e., each agent changes own schedule based on self-satisfaction and sensed pheromone, hich are put according to satisfaction degree of constraints. To adapt the balance between preferences self-satisfaction and sensed pheromone, agents can search good feasible schedules. This mechanism is very simple, but we show the effectiveness of pheromone style communication throughout some experiments.