The paper concerns a small flexible manufacturing system consisting of three CNC machines: a lathe machine, milling machine and measurement center and a single robot, located at the Poznań University of Technology. A short description of the production environment, which can be modeled as the extended job shop system with open shop sections within particular jobs, is followed by the proposition of a branch and bound method. It optimizes production plans within a single shift in order to minimize the late work, i.e. the amount of work executed after a given due date. Based on results of computational experiments, conclusions are formulated on the efficiency of the B&B algorithm and on the behavior of FMS under consideration.
Flexible manufacturing systems (cf. e.g. Ciriani and Leachman, 1993, Kusiak, 1988, Pesch, 1994, Pinedo and Chao, 1999 and Stecke and Suri, 1985) are a very important application field for scheduling theory (cf. e.g. Błażewicz et al., 2001, Brucker, 1998, Chen et al., 1998 and Leung, 2004), which supports solving various problems arising in a production environment from designing a system to managing it efficiently. Most scheduling cases concerning FMSs are computationally hard, since industrial systems usually consist of many specialized machines as well as additional tools and they work under numerous constraints. From the point of view of computational complexity, in general, scheduling problems on more than two specialized machines are NP-hard (cf. e.g. Garey, Johnson, & Sethi, 1976). Similarly, even if a basic scheduling case can be solved in polynomial time taking into account additional parameters, such as release times or weights, makes it intractable (cf. e.g. Lenstra, Rinnooy Kan, & Brucker, 1977). Even evaluating the quality of solutions obtained is a difficult task. Estimating the system performance requires taking into account different points of view, which are usually in conflict, representing interests of system owners as well as its customers
Flexible manufacturing systems are production environments, which give the opportunity to apply different models and techniques developed within scheduling theory. The variety of parameters and constraints describing these systems often inspires theoretical research, e.g. leading to propositions of new models. On the other hand, to solve problems arising in FMSs, it is necessary to adjust and combine creatively results worked out within scheduling theory so far.
In the paper, the studies on the small real flexible manufacturing system were reported. They started from the careful analysis of the production environment, which resulted in the formal model of the system. Restricting the research to a single shift made it possible to propose an exact branch and bound method for the late work minimization in a short time horizon. The late work, representing parts of customer orders realized after pre-defined due dates, have not been yet considered in such a production environment. Computational experiments allowed verifying the efficiency of the B&B approach and of its particular components, especially the list scheduling technique. Moreover, the test results gave the basis for the analysis of the influence of the flexible production processes and setup times on the total late work in the system.
