Dynamically scheduling and maintaining a flexible server

Jefferson Huang
Operations Research Department

Naval Postgraduate School

Douglas G. Down

Department of Computing and Software

McMaster University

Mark E. Lewis

School of Operations Research & Information Engineering
Cornell University
Ithaca, NY 14853

Cheng-Hung Wu

Institute of Industrial Engineering

National Taiwan University

Deciding how to jointly schedule jobs and perform preventive maintenance is a fundamental problem in flexible manufacturing systems, particularly those arising in semiconductor manufacturing. At the same time, past work in this area shows that, even when there is only one station and one type of job, identifying policies that minimize the amount of work-in-process (WIP) is also a difficult problem. In this paper, we study a single-station version of this problem with two types of jobs, with the objective of minimizing average maintenance costs plus the weighted average amount of WIP. We identify conditions under which it suffices to schedule jobs according to both a server-state-dependent version of the c-mu rule, and a static c-mu rule where the average service rates are used. One of these conditions states that the ratio between the service rates should remain constant as the server deteriorates. When this assumption does not hold, scheduling with the c-mu rule can in fact lead to an unstable system; we illustrate this using a simple example. On the other hand, we also present numerical evidence that c-mu based scheduling performs well compared to other scheduling rules, and relative to an “optimal” policy based on solving a Markov decision process.