Modelling and performance of distributed algorithm for scheduling dissimilar machines with set-up

Abstract

Distributed arrival time control is a highly decentralized scheduling approach where each part entity autonomously controls its arrival time to meet the due-date in real time. This paper presents differential equation-based models for distributed arrival time control of parallel dissimilar machines including sequence-dependent set-up and flowshop scheduling. The main objective was to show that the behaviour of general systems under distributed arrival time control was predictable. Convergence properties of the resulting nonlinear systems were established using the theory of discontinuous differential equations. Geometry was used to gain insight into the behaviour of these nonlinear systems. An approximation model was proposed for mean arrival times when the dynamics resulted in a non-unique steady-state. The model was tested using numerical simulation and agreed well. Geometric insights were also used to investigate scheduling performance of distributed arrival time control. Simulation results indicated that distributed arrival time control could provide significant improvement, typically more than 20%, over commonly used dispatching rules for due-date-based measures. Improved predictability and favourable performance made distributed arrival time control an attractive approach for decentralized control of Just-In-Time production.

Acknowledgements

This work was partially supported by the National Science Foundation Grant DMI-9908267 and the Ben Franklin Technology Partner through the Center for Manufacturing Enterprise Integration at Penn State University.

Notes

^†For the case with p_i1<p_j2 for i = 1, … , 3, j = 1, … , 3, i ≠ j.

*p(i, j) denotes the processing time of part i on machine j