Job routing and operations scheduling: a network-based virtual cell formation approach

Virtual cellular manufacturing inherits the benefits of traditional cellula r manufacturing and maintains the responsiveness to the changing market and I outing flexibility of a job shop by integrating machine-grouping, shop l ayout design and intercellular flow handling. The primary goal of virtual c ell formation is to minimize the throughput time of a given job. This paper proposes a method for virtual cell formation by adopting the double-sweep algorithm for the k-shortest path problem, and a heuristic is devised to sc hedule the virtual cells for the multiple job orders. Results generated fro m this method include not only the optimal candidates of the virtual cell w ith the shortest throughput time with sub-optimal alternative route(s) and throughput time(s) as the alternative candidates in case some resources are restricted or are not available. The procedure of virtual cell creation an d scheduling is illustrated explicitly with examples. Since most of the sch eduling problems are NP-hard and virtual cell scheduling is even more compl ex due to the bottleneck machines that are demanded by jobs at other cells. For multiplicity of possible virtual cell candidates, in addition to the p recedence and resource constraints, heuristic solutions are found to be rea sonable.