Workload control in dual-resource constrained high-variety shops: an assessment by simulation

Workload Control (WLC) seeks to align capacity with demand, where capacity is typically assumed to be restricted by a single constraint – machine capacity. In practice, however, shops are often restricted by dual resource constraints: labour and machines. This study, therefore, uses simulation to investigate the performance of WLC in Dual Resource Constrained (DRC) high-variety shops with fully interchangeable labour. By considering several environmental factors and different labour assignment and dispatching rules, it is demonstrated that the order release function of WLC maintains its positive impact on performance in a DRC shop under different staffing levels. The positive effect of considering labour availability at release, as proposed in previous research, could not, however, be confirmed. Thus, the original release method can be applied if labour is fully interchangeable. In terms of labour assignment, we show that a distinct assignment pattern that differs between upstream and downstream stations improves performance if the routing is directed. Meanwhile, dispatching plays a less important role but creates important interaction effects with the assignment rule. Finally, the results suggest that increasing the service rate is a better response to the reduction in capacity that results from labour absenteeism than lowering the input frequency of work.     

A multi-objective procedure for labour assignments and grouping in capacitated cell formation problems

A hierarchical methodology for the design of manufacturing cells is proposed, which includes labour-grouping considerations in addition to partmachine grouping. It is empirically driven and designed for an interactive decision environment, with an emphasis on fast execution times. The method synthesizes the capabilities of neural network methods for rapid clustering of large partmachine data sets, with multi-objective optimization capabilities of mathematical programming. The procedure includes three phases. In Phase I, part families and associated machine types are identified through neural network methods. Phase II involves a prioritization of part families identified, along with adjustments to certain load-related parameters. Phase III involves interactive goal programming for regrouping machines and labour into cells. In machine grouping, factors such as capacity constraints, cell size restrictions, minimization of load imbalances, minimization of intercell movements of parts, minimization of new machines to be purchased, provision of flexibility, etc. are considered. In labour grouping, the functionally specialized labour pools are partitioned and regrouped into cells. Factors such as minimization of hiring and cross-training costs, ensuring balanced loads for workers, minimization of intercell movements of workers, providing adequate levels of labour flexibility, etc. are considered in a pragmatic manner.     

An improved imperialist competitive algorithm based photolithography machines scheduling

Abstract: Photolithography machine is one of the most expensive equipment in semiconductor manufacturing system, and as such is often the bottleneck for processing wafers. This paper focuses on photolithography machines scheduling with the objective of total completion time minimisation. In contrast to classic parallel machines scheduling, it is characterised by dynamical arrival wafers, re-entrant process flows, dedicated machine constraints and auxiliary resources constraints. We propose an improved imperialist competitive algorithm (ICA) within the framework of a rolling horizon strategy for the problem. We develop a variable time interval-based rolling horizon strategy to decide the scheduling point. We address the global optimisation in every local scheduling by proposing a mixed cost function. Moreover, an adaptive assimilation operator and a sociopolitical competition operator are used to prevent premature convergence of ICA to local optima. A chaotic sequence-based local search method is presented to accelerate the rate of convergence. Computational experiments are carried out comparing the proposed algorithm with ILOG CPLEX, dispatching rules and meta-heuristic algorithms in the literature. It is observed that the algorithm proposed shows an excellent behaviour on cycle time minimisation while with a good on time delivery rate and machine utilisation rate.     

Cell formation: the need for an integrated solution of the subproblems

Cellular manufacturing is a viable option in many manufacturing systems. There are various subproblems in the design of a cellular manufacturing system. These are machine group and part family formation, machine duplication, intracell layout and intercell layout. The only comprehensive design strategy that attempts to address all of these is production flow analysis. However, this technique is a sequential strategy where the subproblems mentioned above are assumed nested within each other and are solved in a forward pass with no feedback. This is a satisfactory approach only in cases where the part families are relatively disjoint and machine groups are formed without constraints on machine duplication to eliminate intercell flow. The presence of bottleneck machines and parts renders the problem considerably more complex, as the subproblems influence each other substantially. This paper presents an integrated framework for solving these subproblems by generating a limited set of feasible alternative solutions.     

Family-based scheduling of shops with functional layouts

Simulation studies of job shop scheduling have typically assumed that either setup times are zero (subsumed within the processing time), or that every part has such a unique setup that no setup advantages can be gained by better scheduling policies. These studies also assume that the shop has exactly one copy of every machine. Some researchers have proposed heuristics that explicitly consider setup times and parallel machines in the context of a one stage shop with static arrivals. In contrast, family-based scheduling centred around setup time reduction has been credited with achieving economic savings in batch production industries where GT is employed. We motivate this study by the case of an existing realworld semi-conductor testing facility that has family setups, parallel machines and dynamic job arrival. Using this setting, we investigate whether benefits can still be obtained by using a family-based scheduling philosophy in those environments which do not permit the physical creation of cellular layouts due to the presence of process related or other constraints. We propose and evaluate two new dispatching procedures in a functional job shop that is modelled after the semiconductor testing facility. Results show that a family-based scheduling philosophy centred around coordinating machine setups is advantageous at relatively high setup to processing time ratios, while classic job shop rules suffice otherwise. Based on these results, we present recommendations for managing such environments. We also suggest future research directions in this area.     

Family-based dispatching with parallel machines

Family-based dispatching heuristics seek to lower set-up frequencies by grouping similar types of jobs for joint processing. Hence, job flow times may be improved as less time is spent on set-ups. So far, family-based dispatching with parallel machines received little attention in literature. We address the perceived gap by proposing extensions to existing family-based dispatching heuristics. Main extensions concern improved rules for family priority settings and for coordinating the number of machines in use by a single family. Extended heuristics are tested by an extensive simulation study. Significant performance gains for extended heuristics vs. existing heuristics are found. Performance gains are largest for high set-up to run-time ratios.     

A beam search-based algorithm and evaluation of scheduling approaches for flexible manufacturing systems

This paper presents a new algorithm for the flexible manufacturing system (FMS) scheduling problem. The proposed algorithm is a heuristic based on filtered beam search. It considers finite buffer capacity, routing and sequence flexibilities and generates machine and automated guided vehicle (AGV) schedules for a given scheduling period. A new deadlock resolution mechanism is also developed as an integral part of the proposed algorithm. The performance of the algorithm is compared with several machine and AGV dispatching rules using mean flow time, mean tardiness and makespan criteria. It is also used to examine the effects of scheduling factors (i.e., machine and AGV load levels, routing and sequence flexibilities, etc.) on the system performance. The results indicate that the proposed scheduling algorithm yields considerable improvements in system performance over dispatching rules under a wide variety of experimental conditions.     

Adaptive scheduling and tool flow control in flexible job shops

The recent manufacturing environment is characterized as having diverse products due to mass customization, short production lead-time, and ever-changing customer demand. Today, the need for flexibility, quick responsiveness, and robustness to system uncertainties in production scheduling decisions has dramatically increased. In traditional job shops, tooling is usually assumed as a fixed resource. However, when a tooling resource is shared among different machines, a greater product variety, routing flexibility with a smaller tool inventory can be realized. Such a strategy is usually enabled by an automatic tool changing mechanism and tool delivery system to reduce the time for tooling set-up, hence it allows parts to be processed in small batches. In this paper, a dynamic scheduling problem under flexible tooling resource constraints is studied and presented. An integrated approach is proposed to allow two levels of hierarchical, dynamic decision making for job scheduling and tool flow control in flexible job shops. It decomposes the overall problem into a series of static sub-problems for each scheduling horizon, handles random disruptions by updating job ready time, completion time, and machine status on a rolling horizon basis, and considers the machine availability explicitly in generating schedules. The effectiveness of the proposed dynamic scheduling approach is tested in simulation studies under a flexible job shop environment, where parts have alternative routings. The study results show that the proposed scheduling approach significantly outperforms other dispatching heuristics, including cost over time (COVERT), apparent tardiness cost (ATC), and bottleneck dynamics (BD), on due-date related performance measures. It is also found that the performance difference between the proposed scheduling approach and other heuristics tend to become more significant when the number of machines is increased. The more operation steps a system has, the better the proposed method performs, relative to the other heuristics.     

Performance Evaluation of Hybrid Cells

The existence of intercellular moves due to bottleneck machines is a major road block to higher productivity gains in cellular manufacturing systems. One solution to this problem is the formation of a separate cell containing all bottleneck machines from different machine cells (hybrid cell). The formation of hybrid cell is based on the premise that the concentration of bottleneck machines in a single cell makes them more accessible to exceptional parts and simplifies the material flow. This paper presents a procedure for performance evaluation of hybrid cells with the purpose of verifying this premise. The procedure uses the sum of intercellular and intracellular material handling costs as a performance measure.     

Routing-based reactive scheduling policies for machine failures in dynamic job shops

A scheduling and control system can be viewed as a vital component of modern manufacturing systems that determines companies' overall performance in their respective supply chains. This paper studies reactive scheduling policies developed against unexpected machine failures. These reactive policies are based on rerouting the jobs to their alternative machines when their primary machine fails. Depending on the subset of the jobs considered for rerouting, the long-term performance of four policies are tested under various conditions. Expecting that these rerouting policies would bring an extra load for a material-handling system (MHS), a dynamic job shop environment was studied with and without a MHS. It is shown that the proper selection of a good reactive policy is based not only on the system characteristics such as utilization, machine down times and frequency of machine failures, but also on the MHS capacity (in terms of speed and number of MH devices). The extensive experiments show that when the MHS is not a bottleneck and/or the down times are long enough to compensate the cost of extra rerouting, rerouting all affected jobs to their alternative machines proves to be the best policy. However, when the MHS cannot handle the extra load due to rerouting or the down times are relatively short, then rerouting only the jobs that will arrive to the failed machine during repair performs the best.     

Heuristics for minimizing total weighted tardiness in complex job shops

Semi-conductor manufacturing is arguably one of the most complex manufacturing processes in existence today. A semi-conductor wafer fabrication facility is comprised of batching machines, parallel machines, machines with sequence-dependent set-ups, and re-circulating product flow. The individual job release times and due dates combine with the other processing environment characteristics to form a ‘complex’ job shop scheduling problem. We first present a mixed-integer program (MIP) to minimize total weighted tardiness in a complex job shop. Since the problem is NP-hard, we compare a heuristic based on the MIP (MIP heuristic) with both a tuned version of a modified shifting bottleneck heuristic (SB heuristic) and three dispatching rules using random problem instances of a representative model from the literature. While the MIP heuristic typically produces superior schedules for problem instances with a small number of jobs, the SB heuristic consistently outperforms the MIP heuristic for larger problem instances. The SB heuristic's superior performance as compared to additional dispatching rules is also demonstrated for a larger, ‘real world’ dataset from the literature.     

Bottleneck-based heuristics to minimize tardy jobs in a flexible flow line with unrelated parallel machines

This paper develops new bottleneck-based heuristics with machine selection rules to solve the flexible flow line problem with unrelated parallel machines in each stage and a bottleneck stage in the flow line. The objective is to minimize the number of tardy jobs in the problem. The heuristics consist of three steps: (1) identifying the bottleneck stage; (2) scheduling jobs at the bottleneck stage and the upstream stages ahead of the bottleneck stage; (3) using dispatching rules to schedule jobs at the downstream stages behind the bottleneck stage. A new approach is developed to find the arrival times of the jobs at the bottleneck stage, and two decision rules are developed to schedule the jobs on the bottleneck stage. This new approach neatly overcomes the difficulty of determining feasible arrival times of jobs at the bottleneck stage. In order to evaluate the performance of the proposed heuristics, six well-known dispatching rules are examined for comparison purposes. Six factors are used to design 729 production scenarios, and ten test problems are generated for each scenario. Computational results show that the proposed heuristics significantly outperform all the well-known dispatching rules. An analysis of the experimental factors is also performed and several interesting insights into the heuristics are discovered.     

An integrated scheduling and material-handling approach for complex job shops: a computational study

We suggest an extension of the shifting bottleneck heuristic for complex job shops that takes the operations of automated material-handling systems (AMHS) into account. The heuristic is used within a rolling horizon approach. The job-shop environment contains parallel batching machines, machines with sequence-dependent setup times, and re-entrant process flows. Jobs are transported by an AMHS. Semiconductor wafer fabrication facilities (wafer fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic (SBH) uses a disjunctive graph to decompose the overall scheduling problem into scheduling problems for single machine groups and for transport operations. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). We consider SSPs based on dispatching rules. In this paper, we are also interested in how much we can gain in terms of TWT if we apply more sophisticated SSPs for scheduling the transport operations. We suggest a Variable Neighbourhood Search (VNS) based SSP for this situation. We conduct simulation experiments in a dynamic job-shop environment in order to assess the performance of the suggested algorithms. The integrated SBH outperforms common dispatching rules in many situations. Using near to optimal SSPs leads to improved results compared with dispatching based SSPs for the transport operations.     

Models for Understanding Flexible Manufacturing Systems

The basic features of flexible manufacturing systems are reviewed and models for determining the production capacity of such systems are developed. These models show the desirability of a balanced work load, the benefit of diversity in job routing if there is adequate control of the release of jobs (a job shop can be better than a flow shop), and the superiority of common storage for the system over local storage at machines. The models are extended to allow for material handling delays between machines and for unreliable machines. It is also shown that production capacity models can be used to develop good approximations to the mean number of jobs in the system for given job arrival rates and machine utilizations.     

A novel metric for determining the constraining effect of resources in manufacturing via simulation

This paper provides a novel method for determining the constraining effect of resources in a manufacturing system using discrete event simulation. Traditionally manufacturing systems are constrained by one or more bottlenecks. Eliminating or mitigating the bottleneck will speed up the system throughput. However, bottlenecking resources generally only refer to machines, and primarily focus on flow-shops not job-shops. One important resource we believe that is often overlooked is workers and their associated skills, and we propose that a particular skill could be flagged as a bottleneck resource. We define new metrics known as resource constraint metrics (RCM) for measuring the constraining effect of a resource on the entire manufacturing system. These metrics are flexible and differentiate between the constraining effects of machines and their requested skills. The metrics can also deal with complex workflows with alternative routing, alternative resources, calendars (a necessary consideration when dealing with workers), worker performance, and multiple modes of operation of machines (e.g. run, setup, and maintenance). The use of RCMs in simulation aids in real-world decision-making, by determining which resource should be focussed on and improved to reduce the overall system feeling constrained. This will have the effect of increasing throughput or at least providing the capacity for increased throughput.     

Family-based dispatching: anticipating future jobs

Group Technology exploits similarities in product and process design to meet the diversity of customer demand in an economic way. In this paper we consider one of the implementations of this concept?–?family-based dispatching. Intrinsic to family-based dispatching is the grouping of similar types of products for joint processing. In this way the number of set-ups may be reduced. Consequently, lead-time performance of the shop can be improved. We extend existing rules for family-based dispatching by including data on upcoming job arrivals. Typically, this type of data resides in the minds of the operators, or is stored in a shop-floor control system. Its availability allows for (1) better estimates of the composition of a process batch for a family, (2) the consideration of families for which no products are available at the decision moment, and (3) the possibility to start set-ups in anticipation of future job arrivals. The potential of including forecast data in decision-making is demonstrated by an extensive simulation study of a single-machine shop. Results indicate the possibility of significant improvements of flow time performance.     

Integrating machine scheduling and self-healing maintenance by job-mix pull control

In general, machines degrade with use. But, for some manufacturing processes machine ageing can be reversed by processing alternative types of jobs. In the latter case, machines can run longer without breakdowns if job types are balanced and scheduling is optimised. However, when job arrivals are stochastic, even short-term fluctuations in job mixes can increase the risk of breakdown. This paper presents a proof of concept study on job-mix pull control to exploit the age-reversing, healing effect. Because adding pull control will impact the architecture of factory scheduling, three issues are addressed in the proof. First, it is shown that the new architecture would have a better performance than the existing dispatching approach. Second, a method of pulling jobs from upstream to reduce the probability of machine breakdown is developed. The condition of workload imbalance in which job mix control (JMC) should or should not be activated is analysed. Finally, the benefit of JMC is evaluated by using simulation to demonstrate potential improvements that can be achieved. Besides the proof of concept, this study produces an important finding. A lingering cumulative influence of the self-healing effect is discovered, pointing out a new direction for future maintenance scheduling research.     

Intelligent dispatching for flexible manufacturing

A decision rule for real-time dispatching of parts, each of which may have alternative processing possibilities, has been developed and tested in a simulated flexible manufacturing system. A part, upon completion of an operation, is not routed to a specific machine, but is, in effect, sent to a general queue. Thus, a machine has a global option for choosing parts which in turn may be processed on alternative machines. For effective use of the system's routeing flexibility under these circumstances, the machine needs an intelligent part-selection strategy (rather than shallow heuristics represented by the conventional dispatching rules) that takes into account the current state and trends of the system. The proposed intelligent reasoning procedure has been found to achieve better shop performance than some of the popular dispatching rules, the improved performance being due to the ability to respond to changing circumstances.     

Simulation study of a bottleneck-based dispatching policy for a maintenance workforce

Maintenance is important for production operations and for continuous improvement. Appropriate dispatching of the maintenance workforce to quickly respond to equipment failures and carry out preventive services can improve system productivity. The first-come-first-served policy is typically used in many manufacturing industries. In this paper, we present a priority-based dispatching policy, a dynamic bottleneck policy, based on the analysis of real-time data. In such a policy, priority is assigned to the bottleneck machine after a fixed time period, and the maintenance worker will service the high-priority machine (i.e. bottleneck machine) first when multiple service requests are received. It is shown by extensive simulation experiments that this policy can lead to a greater improvement in system throughput compared with the first-come-first-served policy. To implement such a policy, the appropriate time period for data collection and the frequency for carrying out bottleneck analysis are investigated. In addition, a sensitivity study suggests that the results obtained are insensitive to machine downtime, efficiency, and reliability models.     

汽车维修服务站瓶颈工序的实时调度

在结合优化调度理论和约束理论的基础上,从最小化目标、机器环境、加工特征和约束几方面分析了汽车维修服务站瓶颈工序的实时调度问题的特征,建立了对应的数学模型。根据问题特性,设计了包含复合动态分派规则的启发式调度算法。以实例分析验证了算法的可行性,仿真结果展示了所用算法在优化目标函数值上的优越性和计算时间的可行性。