الگوریتمی برای برنامه ریزی شاخه های قطعات در سیستم تولید انعطاف پذیر چند سلولی

This research addresses the problem of scheduling batches of parts in a flexible manufacturing system (FMS). Due to the use of serial access material-handling systems in many FMSs, the problem is modeled for a multi-cell FMS with flowshop characteristics. A branch and bound solution method is developed which exploits the special structure of the problem to develop strong lower bounds. Numerical computations show that the branch and bound algorithm solves large size problems in a reasonable time. Computational results are provided for a variety of test problems.

The term flexible manufacturing system (FMS) is generally used to indicate a wide variety of automated manufacturing systems. A FMS consists of the following three elements—CNC machine tools, automated material-handling systems, and system control computers. Different classification systems have been used to classify FMSs based on size, level of complexity, type of material-handling system, process characteristics, and scheduling environment (MacCarthy and Liu, 1993; Rachamadugu and Stecke, 1994; Stecke and Browne, 1985). Our study follows MacCarthy and Liu's (1993) FMS classification in examining a scheduling problem for multi-cell flexible manufacturing systems (MCFMS). They define it as: A MCFMS is a type of FMS that consist of a number of flexible manufacturing cell, and possibly a number of single flexible machines, connected by an automated material-handling system. We consider the case where the automated material-handling system in the MCFMS is a serial (i.e., loop or sequential) access type—e.g., belt conveyors, power-and-free conveyors, roller conveyors, monorails/mono-tractors, and towlines. They are relatively fixed route oriented—where a job follows the same route or a few alternative routes in traveling to meet each machine–cell. Modeling of these systems can be done from a flowshop viewpoint. This paper is organized as follows. Section 1.1 looks at the decisions made during the FMS planning stage, reviews the research done in this area, and discusses the need for batching of parts in FMS. Section 2 defines the batch scheduling problem in a MCFMS, reviews relevant FMS scheduling literature, and presents a mathematical model for this problem. Section 3 discusses a branch and bound-based solution procedure to solve the batch scheduling problem. Section 4 presents computational results, while Section 5 presents conclusions and directions for future research. 1.1. Decision making in an FMS environment Stecke and Raman (1995) define three stages of hierarchical decision making in an FMS—design, planning, and scheduling and control decisions. They differentiate between scheduling decisions that are made off-line such as part input sequences, from real-time dispatching decisions. Our research addresses off-line schedule generation that is a FMS planning decision and part of the pre-production system setup (Stecke and Raman, 1995). Other FMS planning decisions include part-type selection decisions, process planning, grouping or pooling of machines, determination of production ratios, batching of parts, scheduling of batches of parts, allocation of pallets and fixtures, and the allocation of operations and tools among machines (Basnet and Minze, 1994; Gunasekaran et al., 1993; Mohamed, 1998; Rachamadugu and Stecke, 1994). When the production of a batch of parts is completed, the planning problem needs to be resolved for a new set of production requirements. A planning period can range from two days to a few weeks. Stecke and Kim (1990) have shown that batching of parts is appropriate for an FMS in a dependent demand environment, where the FMS planning function receives its requirements from a production planning system (e.g., an MRP system), and certain part types are required in particular ratios. Important reasons for batching are: • The tool capacity constraints for each machine, requiring parts to be divided into batches with tool changes in between. • Wear and tear on tools during the machining operations requiring the tool replacement function to be integrated with the batch change-over procedure. • Balancing the workload on each machine tool also necessitates batching to maximize machine tool utilization as well as relieve or avoid potential bottlenecks in the system with the intent of maximizing system throughput. • Batches could be mandated because internal pallet storage is insufficient to handle all parts at once. MacCarthy and Liu (1993) have defined a three-level scheduling hierarchy for a MCFMS. In our research, schedules are being generated off-line during the pre-production, planning phase—i.e., at the top level of their three-level scheduling hierarchy. We assume that the part-type selection problem of selecting a set of part types to be produced in a batch (or group) has been solved prior to scheduling the batches. After batching decisions are made, two types of scheduling decisions must be addressed. The higher level ‘batch scheduling’ decision is to decide the sequence in which batches of parts are to be processed. The next level ‘part scheduling’ decision is to decide the sequence in which the parts are to be processed within each batch. Batch scheduling can be considered as part of the FMS planning stage, while the subsequent disaggregation and individual part scheduling is part of the FMS scheduling and control stage. In this paper, we focus on the higher-level batch scheduling decision, for the different machine–cells in the MCFMS. The subsequent part scheduling decisions inside each cell are not considered here.

The deployment of FMSs has had a major effect on batch manufacturing processes. Scheduling of batches of parts necessitates a system setup from one batch of parts to another, with setup times being dependent on the sequence of batches. In this study we defined the problem for scheduling batches of parts in a multi-stage MCFMS that explicitly considers sequence dependent setup times between batches, and developed a branch and bound procedure to solve this batch scheduling problem. We used this procedure to solve a variety of test problems (both small and large sizes) optimally. We validated the branch and bound procedure by testing over a number of problems obtained from the literature and randomly generated for testing purposes, and were able to solve problems with 10 batches and 20 cells (n=10, m=20). Small size problems were solved in a few minutes, while solving large size problems having n>9, required several hours. The case of the batch scheduling problem in a MCFMS with random access material handling systems (e.g., automatic guided vehicles) can be modeled as a job shop-type scheduling problem with sequence-dependent setup times. This problem has been addressed by using one of two simplifying techniques: batching of similar parts, and creating cells to manufacture families of similar batches (i.e., group technology and cellular manufacturing practices, which has been extensively studied in the literature); or the batching of jobs and creating a logical (as opposed to a physical) flowshop-type arrangement of cells for batches of parts in the FMS, which is similar to the type of problem solved in this research. Another type of problem involves the presence of buffers between workstations in the FMS. In this case, if a batch is being processed in a cell and subsequent batches arrive from the previous cell and wait, the choice of the next batch to be processed may not follow a permutation schedule. Therefore the order of batches to be processed in a cell may not be the same on every cell making the problem more difficult to solve. The processing times of batches could be stochastic with variable lead times, necessitating the use of queuing models to solve the problem. Though our objective has been the minimization of makespan, other scheduling objectives can also be used for this problem. These include criteria based on due dates (tardiness, lateness, number of late batches, etc.), inventory levels, and costs. These different types of FMS planning problems represent an area with a rich potential for research.