FMS-scheduling using branch-and-bound with heuristics on a transputer system

Flexible production systems require large investments which implies that their optimal utilization is mandatory for their economic success. We deal with the optimal on-line allocation of the most costly resources, the machines, in such systems. Optimality is defined with respect to given due dates for the production of certain parts or batches of parts. The system may have machines with overlapping or identical functionality. The on-line scheduling refers to the fact that decisions cannot be made aforehand but have to be based on the actual situation of the system which may change at any instant due to the introduction of new jobs, changes of due dates, or disturbances or deviations from the nominal operation. Such scheduling problems are known to be NP-hard and thus optimization is in general not possible exect of very simple cases. Therefore, we developed an algorithm based on the branch-and-bound principle and uses heuristics to cope with the complexity. For improving the run time b ehavior of our algorithm we parallelized our modified branch-and-bound algorithm and realized it on a transputer system. Our transputer system has only four transputers and we reached a speed up over three and an efficiency of nearly 0,8.