CYCLIC SCHEDULING IN A STOCHASTIC ENVIRONMENT

Cyclic or periodic schedules can be implemented in a job shop where de mands for various products have a stable rate and mix. Numerous result s on cyclic scheduling in deterministic settings are available, but st udies considering uncertainties such as machine failure are rare. This paper examines the behavior of cyclic schedules in a stochastic envir onment characterized by random machine failures that may delay executi on of tasks and thus may cause the actual production to deviate from a specified cyclic schedule. The authors intend to understand the behav ior of cyclic schedules under uncertainty and to find those cyclic sch edules that are the least disturbed by occurrences of machine failure. The cyclic scheduling problem of one or multiple machines can be form ulated into a convex program for which the objective is to minimize a weighted sum of expected ergodic delays experienced by tasks. For one- machine schedules, the ergodic distributions of delays, as well as the ir expected values, are displayed. For multiple-machine schedules, a n ecessary condition for ergodicity is presented and stochastic lower bo unds on task delays are derived.