Optimal Scheduling Control of a Flexible Machine

A flexible machine that processes a set of different part types is considered. Each part type has its own Poisson arrival process, general processing requirement, and a given delay (flow time) constraint. The problem is to find an optimal control that schedules the machine among the part types on a real time basis in order to minimize a cost function of the flow times and meet all the constraints. The cost function is quite general, and it only requires that the marginal costs can be ordered among the part types. Based on polymatroid theory, an optimal control is identified that partitions the part types into several groups and applies a priority rule among the groups. Within each group, the optimal control is an appropriate randomization among priority rules. An efficient algorithm is developed to completely characterize the optimal control. © 1990 IEEE