| Flexible manufacturing systems must be able to respond to unexpected events. Polite rescheduling is an intelligent way for a manufacturing cell controller to respond to schedule disruptions (e.g., machine break-down or new job arrival), when other cells in the manufacturing system may be adversely affected by the response. Local schedules at different cells may interact through resource sharing and precedence constraints; thus, local scheduling changes at one cell may disrupt schedules at other cells. At worst, one local schedule disruption may propagate throughout the entire system. The polite rescheduling approach attempts to respond to schedule disruptions so that other agents are disrupted as little as possible, and so that the propagation of disruptions can be contained. This approach has the advantage of retaining much of any original distributed plan.;Reasoning about how local scheduling decisions may affect other cells often requires information about other cells' states that is not available locally. Negotiation with other possibly-affected cells may be necessary for determining which local scheduling decisions are most appropriate. Polite rescheduling thus brings together ideas and techniques from the fields of distributed artificial intelligence, factory scheduling, and plan revision. It requires reasoning about global constraints on local scheduling decisions, about how negotiation with other cells may be pursued efficiently, and about how current schedules may be modified to satisfy new requirements.;We apply this concept to the domains of tool management and scheduling, and job shop scheduling, and evaluate the proposed method through simulation. We show that polite rescheduling, which is local rescheduling using local knowledge, performs close to good or optimal methods that use global information, when workcells are loosely-coupled; our method is appropriate for example when workcells share one or two tools, or in job shops in which work tends to flow in one direction. We also propose PRIAM, a polite rescheduling architecture, in which a negotiator module determines scheduling priorities through evaluation of local information and information gathered through negotiation, and a rescheduler module, which uses various scheduling methods to produce a revised schedule with these priorities in mind. We investigate various ways priorities can be determined using local knowledge or uncertain information about remote cells' requirements, and various scheduling methods by which constraints imposed by remote cells can be satisfied. |
