Assuming given production requirements for a set of part types, we examine the question of how these production requirements can be assigned to different, alternative routes through two production systems, a flexible manufacturing system, and a conventional job shop. Several nonlinear optimization models are proposed in order to optimize performance parameters like throughput, work-in-process inventory, utilization, and manufacturing lead time. The models incorporate product form queueing network theory in order to evaluate system performance and extend results based on linear programming formulations. The solution procedures are based on decomposition, fixed point, and classical gradient search techniques.

This paper examines the minimum makespan problem for the job shop from an artificial intelligence point of view. A new solution procedure is presented which combines general learning strategies with special purpose heuristics, i.e., a constraint propagation based procedure is used and by decomposing the whole problem into single machine problems, problem specific knowledge is introduced. Fundamental for this approach is the equivalency between the constraint and the disjunctive graph. Presented comprehensive computational tests show high quality partial solutions, substantially accelerated exact methods, and a gain of deeper insight into the nature of the underlying problem instances. For example, the propagation and decomposition techniques reveal the particular structure underlying the well-known Fisher and Thompson 10 × 10 problem and thus provide an explanation for why this problem was intractable for such a long time.