Abstract
The use of cyclic schedules for manufacturing systems, particularly ones with fairly stable demand, has been found to have several advantages over other methods of scheduling. These advantages include ease of communication to the shop floor, consistency with the just-in time philosophy, and less myopic nature. When a cyclic schedule is put in place, additional structure is imposed on the system, and precedence relations are established between operations. We exploit the structure of the cyclically scheduled manufacturing facility by modelling the system as an acyclic directed network, whose arc lengths correspond to the durations of the various production operations. By computing the longest path through the network, we obtain the start times of the operations, as well as a good estimate of the time needed to meet a specified demand. This time can then be compared with a desired due date to determine if the due date can be met. For the situation where the due date cannot be met, we formulate the problem of expending additional resources, such as overtime and subcontracting of parts, to meet the due date, as a linear program. We describe an efficient algorithm based on Dantzig-Wolfe decomposition, to solve the potentially large problem of finding the least cost combination of additional resources needed to meet the demand by the due date. Finally, we give the results of a computational test of the algorithm using two sets of complex and realistic factory data.
Notes
†To whom correspondence should be addressed.