Evaluations of operational control rules in scheduling a flexible manufacturing system

In this paper, computer simulation is used to evaluate the effects of various control rules on the performance of a flexible manufacturing system (FMS) operating under different manufacturing environment. Alternative routings are available, if the operation of a part can be performed by more than one machine. Three control rules, namely, dynamic alternative routings, planned alternative routings, and no alternative routings, are proposed to control the selection of alternative routings for each part. The effects of the universal loading station and also those of the dedicated loading station are investigated. In addition, the impact of buffer existence on the system’s performance is also examined by considering machines with and without local buffers. The effects of changing production ratios of different part types on the performance of various operational control rules are also investigated. Moreover, the effects of system having machine breakdown are also discussed. The simulation results indicate that the FMS with dedicated loading stations outperforms the FMS with universal loading stations in all aspects. The dynamic alternative routings generally produces the best results in system performance if the universal loading station is provided. The planned alternative routings generally gives the best system performance when both the dedicated loading stations and local buffers are available. The no alternative routings usually remains at the bottom of the rank, occasionally with some exceptions. Problems in actual implementation are also highlighted.     

Process plan and part routing optimization in a dynamic flexible job shop scheduling environment: an optimization via simulation approach

This paper presents an optimization via simulation approach to solve dynamic flexible job shop scheduling problems. In most real-life problems, certain operation of a part can be processed on more than one machine, which makes the considered system (i.e., job shops) flexible. On one hand, flexibility provides alternative part routings which most of the time relaxes shop floor operations. On the other hand, increased flexibility makes operation machine pairing decisions (i.e., the most suitable part routing) much more complex. This study deals with both determining the best process plan for each part and then finding the best machine for each operation in a dynamic flexible job shop scheduling environment. In this respect, a genetic algorithm approach is adapted to determine best part processing plan for each part and then select appropriate machines for each operation of each part according to the determined part processing plan. Genetic algorithm solves the optimization phase of solution methodology. Then, these machine-operation pairings are utilized by discrete-event system simulation model to estimate their performances. These two phases of the study follow each other iteratively. The goal of methodology is to find the solution that minimizes total of average flowtimes for all parts. The results reveal that optimization via simulation approach is a good way to cope with dynamic flexible job shop scheduling problems, which usually takes NP-Hard form.     

Automated system for machine tool capacity and utilization

An automated system based on Symphony spreadsheet software has been developed to monitor machine tool utilization and capacity in a small- to medium-sized machine shop. This application compiles reports on annual machine tool requirements and use from production routing data for a shop producing over 100 different small machined parts with batch sizes ranging from 100 to 1000 parts and up to 25,000 parts per year. The operational routings for approximately 30 parts are currently stored in the system. Levels of utilization are analyzed, which aids in determining the need for addition equipment or multiple workshifts, and thereby helps balance the workload and product flow. Valuable information was compiled in a special report for layout of a new shop facility. Group technology cell arrangements of equipment were analyzed for capacity and utilization. Many Symphony spreadsheet and data base management features were used to produce this program. The final system incorporated menu systems for users unfamiliar with this spreadsheet software.     

A closed-loop control architecture for CAM accounting for shop floor uncertainties

The primary focus of this paper is to demonstrate an enhanced closed-loop computer-aided manufacturing (CAM) architecture using a Petri net based analysis mechanism, which incorporates shop floor uncertainties to generate process plans and alternative processing sequences under dynamic conditions such as machine failures. Modern CAM software provide efficient, error-free, and user-friendly interfaces to develop processing sequences for manufacturing tasks. However, their effective scope is still limited from the post-process planning stage to the pre-machining stage. These types of software fail to incorporate the variability encountered in an actual shop floor to develop effective process plans. This is caused due to CAM software’s limitations in input handling mechanisms, limited simulation functionality, and inability to handle complex process variability from the shop floor. In this paper, CAM functionality is augmented with Petri net models to capture alternative process plans and shop floor variability arising due to equipment failures, repairs, and setups. The output from the analysis of the Petri net model provides a better understanding of the process characteristics and provides information to the CAM system to adapt to shop floor variability. The resulting information from the Petri net model allows the CAM system to compare alternative process plans while taking shop floor information into account. This mechanism can result in better decisions, reduced processing times, and better overall resource utilization, and provide alternative process plans based on current resource information.     

Analysis of dynamic control strategies of an FMS under different scenarios

This paper presents a simulation study aimed at evaluating the performances of a flexible manufacturing system (FMS) in terms of makespan, average flow time, average delay time at local buffers and average machine utilization, subject to different control strategies which include routing flexibilities and dispatching rules. The routing strategies under evaluation are ‘no alternative routings’; ‘alternative routings dynamic’; and ‘alternative routings planned’. Above routing strategies are combined with seven dispatching rules, and studied in different production volume which varies from 50 to 500 parts. In addition, impacts of both infinite and finite local buffer capacities are analyzed. Since an FMS usually deals with a variety of products, effects of changing the part mix ratio are also discussed. Finally, machine failure is also introduced in this research to study the effects of machine reliability on the system. Simulation results indicate that the ‘alternative routings planned’ strategy outperforms other routing strategies if the local buffer size is infinity. However, there is no particular dispatching rule that performs well in all buffer size settings but infinity buffer size is not the best choice with respect to the four performance measures. In addition, the four performance measures, except machine utilization, under different control strategies seem quite insensitive to the variation in part mix ratios.     

On the Complexity of Non-preemptive Shop Scheduling with Two Jobs

In this note, we investigate the time complexity of non-preemptive shop scheduling problems with two jobs. First we study mixed shop scheduling where one job has a fixed order of operations and the operations of the other job may be executed in arbitrary order. This problem is shown to be binary NP-complete with respect to all traditional optimality criteria even if distinct operations of the same job require different machines. Moreover, we devise a pseudo-polynomial time algorithm which solves the problem with respect to all non-decreasing objective functions. Finally, when the job with fixed order of operations may visit a machine more than once, the problem becomes unary NP-complete. Then we discuss shop scheduling with two jobs having chain-like routings. It is shown that the problem is unary NP-complete with respect to all traditional optimality criteria even if one of the jobs has fixed order of operations and the jobs cannot visit a machine twice. Received July 28, 2001; revised May 15, 2002 Published online: July 26, 2002     

An efficient tabu search algorithm to the cell formation problem with alternative routings and machine reliability considerations

Cell formation is the first step in the design of cellular manufacturing systems. In this study, an efficient tabu search algorithm based on a similarity coefficient is proposed to solve the cell formation problem with alternative process routings and machine reliability considerations. In the proposed algorithm, good initial solutions are first generated and later on improved by a tabu search algorithm combining the mutation operator and an effective neighborhood solution searching mechanism. Computational experiences from test problems show that the proposed approach is extremely effective and efficient. When compared with the mathematical programming approach which took three hours to solve problems, the proposed algorithm is able to produce optimal solutions in less than 2 s.     

Clustering algorithm for solving group technology problem with multiple process routings

Cell formation is an important problem in the design of a cellular manufacturing system. Most of the cell formation methods in the literature assume that each part has a single process plan. However, there may be many alternative process plans for making a specific part, specially when the part is complex. Considering part multiple process routings in the formation of machine-part families in addition to other production data is more realistic and can produce more independent manufacturing cells with less intercellular moves between them. A new comprehensive similarity coefficient that incorporates multiple process routings in addition to operations sequence, production volumes, duplicate machines, and machines capacity is developed. Also, a clustering algorithm for machine cell formation is proposed. The algorithm uses the developed similarity coefficient to calculate the similarity between machine groups. The developed similarity coefficient showed more sensitivity to the intercellular moves and produced better machine grouping.     

An efficient approach to determine cell formation,cell layout and intracellular machine sequence in cellular manufacturing systems

Cellular manufacturing systems (CMS) are used to improve production flexibility and efficiency. They involve the identification of part families and machine cells so that intercellular movement is minimized and the utilization of the machines within a cell is maximized. Previous research has focused mainly on cell formation problems and their variants; however, only few articles have focused on more practical and complicated problems that simultaneously consider the three critical issues in the CMS-design process, i.e., cell formation, cell layout, and intracellular machine sequence. In this study, a two-stage mathematical programming model is formulated to integrate the three critical issues with the consideration of alternative process routings, operation sequences, and production volume. Next, because of the combinatorial nature of the above model, an efficient tabu search algorithm based on a generalized similarity coefficient is proposed. Computational results from test problems show that our proposed model and solution approach are both effective and efficient. When compared to the mathematical programming approach, which takes more than 112 h (LINGO) and 1139 s (CPLEX) to solve a set of ten test instances, the proposed algorithm can produce optimal solutions for the same set of test instances in less than 12 s.     

A distributed scheduling and shop floor control method

We suggest a market-like framework for scheduling and shop floor control in computer-controlled manufacturing systems where each resource agent and part agent acts like an independent profit maker. A part-resource negotiation procedure is suggested including price-based bid construction and price revising mechanism. Alternative routings for each production order are considered in scheduling and shop floor control. A simulation-based scheduling method is suggested to estimate the start time and the completion time of each task. We develop a prototype soffivare which utilizes the object-oriented concept.     

A multiple-objective grouping genetic algorithm for the cell formation problem with alternative routings

This paper addresses the cell formation problem with alternative part routings, considering machine capacity constraints. Given processes, machine capacities and quantities of parts to produce, the problem consists in defining the preferential routing for each part optimising the grouping of machines into manufacturing cells. The main objective is to minimise the inter-cellular traffic, while respecting machine capacity constraints. To solve this problem, the authors propose an integrated approach based on a multiple-objective grouping genetic algorithm for the preferential routing selection of each part (by solving an associated resource planning problem) and an integrated heuristic for the cell formation problem.     

A genetic algorithm-based scheduler for multiproduct parallel machine sheet metal job shop

This paper presents a genetic algorithm-based job-shop scheduler for a flexible multi-product, parallel machine sheet metal job shop. Most of the existing research has focused only on permutation job shops in which the manufacturing sequence and routings are strictly in a predefined order. This effectively meant that only the jobs shops with little or no flexibility could be modeled using these models. The real life job shops may have flexibility of routing and sequencing. Our paper proposes one such model where variable sequences and multiple routings are possible. Another limitation of the existing literature was found to be negligence of the setup times. In many job shops like sheet metal shops, setup time may be a very sizable portion of the total make-span of the jobs, hence setup times will be considered in this work. One more flexibility type arises as a direct consequence of the routing flexibility. When there are multiple machines (parallel machines) to perform the same operation, the job could be routed to one or more of these machines to reduce the make-span. This is possible in situations where each job consists of a pre-defined quantity of a specified product. In other words, same job is quantity-wise split into two or more parts whenever it reduces the makespan. This effectively assumes that the setup cost is negligible. This model has been implemented on a real-life industry problem using VB.Net programming language. The results from the scheduler are found to be better than those obtained by simple sequencing rules.     

An approach to regulating machine sharing in reconfigurable back-end semiconductor manufacturing

By complying with the operational philosophy of virtual production lines, a back-end semiconductor manufacturing system can be controlled and managed with better reconfigurability. However, due to the absence of a fully-integrated information system and the gaining popularity of distributed computing, machine reconfiguration decisions are made by machine controllers on the shop floor where heterarchical control architecture is typically used. This research investigates how non-cooperative game theory could be applied for facilitating the decision process reconfiguration decision-making at the machine controller level as machines are competed by multiple jobs streams. This paper presents how material flow traffic can be better regulated in a reconfigurable manufacturing environment. A study using an industrial pilot system is discussed to demonstrate the applicability of the proposed approach, in which heuristics are used to determine the game specification.     

求解柔性作业车间调度的GATOC混合方法

柔性作业车间调度问题是经典作业车间调度问题的扩展,它允许工序在可选加工机器集中任意一台上加工,加工时间随加工机器不同而不同。针对柔性作业车间调度问题的特点,提出一种基于约束理论的局部搜索方法,对关键路径上的机器的负荷率进行比较,寻找瓶颈机器,以保证各机器之间的负荷平衡。为了克服传统遗传算法早熟和收敛慢的缺点,设计多种变异操作,增加种群多样性。为了更好保留每代中的优良解,设计了基于海明距离的精英解保留策略。运用提出的算法求解基准测试问题,验证了算法的可行性和有效性。     

求解考虑机器调整时间的并行机分批优化调度问题

基于目前车间调度问题是以单个或整批进行生产加工的并行机调度模型已不再符合实际工况下的车间生产。提出以最小化最大完工时间为优化目标,对遗传差分进化混合算法,灰狼差分进化混合算法进行了比较。为提高加工工件进行分批及分批之后子批的分配与排序效率,该问题是对不同规模的经典并行机调度问题进行求解并展示两种算法的求解,证明了灰狼差分进化混合算法在寻优性能上优于遗传差分进化混合算法,不仅具有更好的解的稳定性,而且具有更高的寻优精度。     

Formation of part families to design cells with alternative routing considerations

A heuristic algorithm for the formation of part families to design cells with consideration to alternative routing of parts is presented. Most of the existing algorithms in cellular manufacturing systems utilize fixed routings for parts. Consideration of alternative routings in the design of cells is important for improving operational aspects of cellular manufacturing systems. An example problem solved is included in the paper.     

A machine learning approach to predict production time using real-time RFID data in industrialized building construction

Industrialized building construction is an approach that integrates manufacturing techniques into construction projects to achieve improved quality, shortened project duration, and enhanced schedule predictability. Time savings result from concurrently carrying out factory operations and site preparation activities. In an industrialized building construction factory, the accurate prediction of production cycle time is crucial to reap the advantage of improved schedule predictability leading to enhanced production planning and control. With the large amount of data being generated as part of the daily operations within such a factory, the present study proposes a machine learning approach to accurately estimate production time using (1) the physical characteristics of building components, (2) the real-time tracking data gathered using a radio frequency identification system, and (3) a set of engineered features constructed to capture the real-time loading conditions of the job shop. The results show a mean absolute percentage error and correlation coefficient of 11% and 0.80, respectively, between the actual and predicted values when using random forest models. The results confirm the significant effects of including shop utilization features in model training and suggest that predicting production time can be reasonably achieved.     

Group shops scheduling with makespan criterion subject to random release dates and processing times

This paper deals with a stochastic group shop scheduling problem. The group shop scheduling problem is a general formulation that includes the other shop scheduling problems such as the flow shop, the job shop and the open shop scheduling problems. Both the release date of each job and the processing time of each job on each machine are random variables with known distributions. The objective is to find a job schedule which minimizes the expected makespan. First, the problem is formulated in a form of stochastic programming and then a lower bound on the expected makespan is proposed which may be used as a measure for evaluating the performance of a solution without simulating. To solve the stochastic problem efficiently, a simulation optimization approach is developed that is a hybrid of an ant colony optimization algorithm and a heuristic algorithm to generate good solutions and a discrete event simulation model to evaluate the expected makespan. The proposed approach is tested on instances where the random variables are normally, exponentially or uniformly distributed and gives promising results.     

Machining times and costs analyzed on a programmable calculator

Two sets of programs for analyzing machine shop operations have been developed for application by a programmable calculator. The first set generates time standards for a wide variety of metal cutting and grinding operations: the second per performs an analysis of the costs of labor, machinery, and tooling.Thiis latter analysis also produces the optimum machine speed to employ to minimize production time or cost, or to maximize profit.