Family based dispatching with batch availability

Family based dispatching rules seek to lower set-up frequencies by grouping (batching) similar types of jobs for joint processing. Hence shop flow times may be improved, as less time is spent on set-ups. Motivated by an industrial project we study the control of machines with batch availability, i.e. all the jobs of the same batch become available for processing and leave the machine together. So far the literature seems to have neglected this type of shop by restricting its focus on machines with item availability, i.e. assuming machine operations concern single jobs. We address this gap by proposing extensions to existing family based dispatching rules. Extended rules are tested by an extensive simulation study. Best performance is found for non-exhaustive rules, which allow for alternative choices of batch size. Performance gains are highest for low set-up to run-time ratios and/or high workloads.     

Coordinating batching decisions in manufacturing networks

Family-based dispatching heuristics aim for improving job flow times by reducing time spent on set-ups. They realise set-up efficiencies by batching similar types of jobs. By their intuitiveness and the simplicity of their decision logic, they may contribute to an easy to implement and viable strategy in many practical settings. Similar to common dispatching rules most existing family-based dispatching heuristics are myopic, i.e. their decision scope is restricted to a single manufacturing stage. Hence, they neglect opportunities for improving shop performance by coordinating batching decisions with other manufacturing stages. Case examples from industry underpin the need for exploring these opportunities. We do so by studying a simple two-stage flow shop, entailing a serial and a batch stage. To facilitate shop coordination we propose extensions to existing family-based dispatching heuristics. Extended heuristics seek to further increase set-up efficiencies by allowing for upstream job re-sequencing, and pro-active set-ups, i.e. set-ups that may be initiated prior to the arrival of a job. Outcomes of an extensive simulation study indicate significant performance gains for extended heuristics vs. existing heuristics. Performance gains are largest for moderate and high set-up to run-time ratios.     

A batch splitting method for a job shop scheduling problem in an MRP environment

The job shop scheduling problem has been a major target for many researchers. Unfortunately though, most of the previous research was based on assumptions that are different from the real manufacturing environment. Among those distorted assumptions, two assumptions about set-up time and job composition can greatly influence the performance of a schedule. First, most of the past studies ignored the impact of the before-arrival set-up time. If we know the sequence of operations in advance, we can obtain an improved schedule by preparing the setup before a job arrives. Secondly, most of the past studies assumed that a job consists of only a single part, that is a batch of size one. However, if we assume that a job consists of a batch size greater than one, as in many real manufacturing environments, then we can obtain an improved schedule because we can fill up the idle times of machines with jobs which have smaller processing times by splitting the original batches. However, the number of job orders may then increase due to the split, and the size of the scheduling problem would become too large to be solved in a practical time limit. Consequently, there may be an optimum batch size considering trade-off between better solution and tractability. The current study is the result of an attempt to find an acceptable solution when the production requirement from a MRP system for a planning period exceeds the capacity of a production system. We try to get an improved schedule by splitting the original batch into smaller batches, and consider setting up a machine before the actual arrival of jobs to that machine. Thereby we can meet the due date requirement without resorting to rescheduling of the master production schedule. For the given batch, we disaggregate it according to the algorithm we are proposing. A so-called 'modified shifting bottleneck procedure' is then applied to solve the job shop scheduling problem with a before-arrival family set-up time considering release date, transportation time and due date. The study also shows that we can adapt to unexpected dynamic events more elegantly by allowing the splitting of batches.     

A comparison of focused cellular manufacturing to cellular manufacturing and job shop

The purpose of this study is to compare a focused cellular manufacturing environment with traditional cellular manufacturing, and job shop environments. We define focused cellular manufacturing as a configuration scheme that groups components by end-items and forms cells of machines to fabricate and assemble end-items. In addition, this research includes three levels of batch sizes and two levels of set-up times in its performance criteria which few researchers in this area have done. The results indicate that the focused cellular manufacturing scheme has a batching advantage. This advantage dominated the balanced machine utilization benefit of the job shop configuration scheme and out weighed the set-up time reduction advantage of the cellular manufacturing scheme for average end-item completion times and average work-in-process inventory levels. The cellular manufacturing and job shop schemes overcame the batch size advantage only when batch sizes were small or set-up times were large.     

A comparison of sequencing rules in static and dynamic hybrid flow systems

It is well known that efficient scheduling of jobs is essential for improving the economics of production in manufacturing organizations. As a result, extensive research has been conducted on scheduling, especially in job shop and flow shop settings. In contrast, little research has been done on hybrid flow systems, even though they are found in many industries, including beer processing, glass container production, pertroleum refining, plastic-coated cable production, and fertilizer production. Furthermore, the few studies that have dealt with hybrid systems have been limited by the assumptions made about their operating environments. Therefore, we conducted a study that extends the previous work on hybrid systems in two significant ways: (1) it included financially oriented scheduling rules and a new, related performance measure; and (2) the new rules were compared with the existing ones in a large simulation experiment under both static and dynamic (generally encountered in practice) hybrid flow shop environments. To date such comparisons have been made only under static environments. The results show that the relative performances of the scheduling rules differ as the assumptions regarding the operating environment are changed.     

Family based dispatching in manufacturing networks

Intrinsic to family based dispatching is the grouping of similar types of jobs in front of a machine for joint processing. Machine flow times may be improved in this way, as less time is spent on set-ups. Our observations in practice, however, suggest that family based dispatching may result in a bulky arrival pattern for successor manufacturing stages, thereby causing additional delay. So far, literature seems to neglect this effect. To explore this issue we develop queuing theoretical approximations of flow times for a simple two-stage shop. It appears that the optimal batch size for the shop is typically smaller than the optimal batch size for the batch machine. Furthermore, we propose extensions to existing dispatching rules by using information on successor stages. Existing and new extended rules are tested by an extensive simulation study. In line with the queuing theoretical analysis the outcomes indicate that exhaustive rules – assuming batch size to be equal to family queue length – are clearly outperformed by non-exhaustive rules – allowing for smaller batches. Moreover, results show that the inclusion of local information on successor stages in rule decision making improves shop flow times.     

Cyclic scheduling heuristics for a re-entrant job shop manufacturing environment

Two efficient cyclic scheduling heuristics for re-entrant job shop environments were developed. Each heuristic generated an efficient and feasible cyclic production schedule for a job shop in which a single product was produced repetitively on a set of machines was to determine an efficient and feasible cyclic schedule which simultaneously minimized flow time and cycle time. The first heuristic considered a repetitive production re-entrant job shop with a predetermined sequence of operations on a single product with known processing times, set-up and material handling times. The second heuristic was a specialization of the first heuristic where the set-up for an operation could commence even while the preceding operation was in progress. These heuristics have been extensively tested and computational results are provided. Also, extensive analysis of worst-case and trade-offs between cycle time and flow time are provided. The results indicate that the proposed heuristics are robust and yield efficient and superior cyclic schedules with modest computational effort.     

Improving the applicability of workload control (WLC): the influence of sequence-dependent set-up times on workload controlled job shops

Simulation has demonstrated that the workload control (WLC) concept can improve performance in job shops, but positive empirical results are scarce. A key reason for this is that the concept has not been developed to handle a number of practical considerations, including sequence-dependent set-up times. This paper investigates the influence of sequence-dependent set-up times on the performance of a workload-controlled job shop. It introduces new set-up-oriented dispatching rules and assesses the performance impact of controlled order release. Simulation results demonstrate that combining an effective WLC order release rule with an appropriate dispatching rule improves performance over use of a dispatching rule in isolation when set-up times are sequence dependent. The findings improve our understanding of how this key implementation challenge can be overcome. Future research should investigate whether the results hold if set-up time parameters are dynamic and set-up times are not evenly distributed across resources.     

A simulation comparison of group technology with traditional job shop manufacturing

A simulation model of an actual job shop was used to compare group technology with traditional job shop manufacturing. The experiment compared shops which had four different layouts, designed to emphasize different features of traditional job shops and group technology shops, and four distributions of demand for end items. The group technology shops exhibited superior performance in terms of average move time and average set-up time. The traditional job shops had superior performance in queue related variables (average queue length, average waiting time, work-in-process inventory, etc.). This was caused by group technology's dedication of machines. The effects of the queue related variables outweighed the effects of average move time and average set-up time: the average flow time was shorter in the traditional job shop than in the group technology shops.     

基于规则和仿真的多机并行作业车间生产调度研究

资源分派和能力分派是作业车间生产调度中的重要问题,路径选择规则和分派规则是解决上述问题的有效途径。采用基于规则的仿真研究多机并行作业车间资源分派和能力分派问题,分析工件加工时间、到达率以及机器加工速率对调度结果的影响,以平均完工时间、平均延迟交货率以及平均资源利用率为评价指标,通过对4种路径选择规则和6种分派规则的仿真试验,确定不同性能指标下最佳的调度规则。仿真研究表明:调度规则的选用取决于车间资源配置和调度目标,应避免仅凭借经验或偏好选择规则的调度方法。     

Non-exhaustive family based dispatching heuristics–exploiting variances of processing and set-up times

Group technology exploits similarities in product and process design to effectively meet the diversity of customer demand. In this paper we consider one of the implementations of this concept–heuristics for family based dispatching. Intrinsic to family based dispatching is the grouping of similar types of products for joint processing. Hence, the number of set-ups may be reduced. Consequently, lead time performance of the shop can be improved. Unfortunately, variances of processing and set-up times–as found in practice–have received little attention in heuristics’ construction and testing. To address this issue we propose several new, non-exhaustive heuristics. Whereas existing exhaustive heuristics set batch contents equal to all products available for a family, non-exhaustive heuristics allow for switching families, even when the current family queue is not empty. An extensive simulation study shows how this flexibility in batch composition improves shop performance, especially in case of high variances of processing and set-up times.     

Lead time prediction in unbalanced production systems

Whether job due dates are set internally or externally, it is critical for the shop floor controller to be able to accurately predict job lead times. Previous research has shown that utilizing information on the congestion levels along a job's route is more valuable than overall shop congestion levels when predicting job lead times. While this information is easily attained in a simulation model, in industrial applications the task may be considerably more difficult, especially when lot splitting is used to accelerate material flow. We examine the effectiveness of three lead time estimation procedures which utilize different shop information in bottleneck-constrained production systems where lot splitting is practiced under a variety of experimental conditions. The results indicate that accurate lead time estimates can be obtained using information pertaining solely to the bottleneck work centre when the bottleneck is at an entry work centre. This offers operations managers a substantial ease in implementation over previously reported methods. The results also show that the operations managers interested in accurately estimating job lead times are well advised to take advantage of the excess capacity at non-bottleneck work centres by performing additional setups, and take measures that reduce bottleneck shiftiness.     

Analysis of group technology scheduling heuristics

The need for increased productivity in small batch manufacturing has recently brought focus to the topics and concepts of group technology. The results of a simulation analysis of the use of three job shop simulation scheduling rules which focus on inducing efficiency in the shop is presented. Two of these rules show significant gains in efficiency and, unexpectedly, they also show significant gains in effectiveness. These rules, in effect, induce the efficiency gains expected with group technology implementation.     

优化交货可靠性的装配作业车间分批调度

装配作业车间生产多规格小批量装配型产品,通常具有差异BOM结构,主要由客制零件组成,但同规格产品仍然包含一定比例的可互用零件,每类零件具有一定批量。此类车间分批调度需要最优化零件类的批次分割和子批加工序列。考虑客户对高交货可靠性的需求,构建了基于最优化交货可靠性为决策优化目标的分批调度数学模型,建立了基于遗传算法和优先级分派规则的混合求解算法。最后通过仿真实验分析和验证了所提方法的有效性。     

A comparative study of priority dispatching rules in a hybrid assembly/job shop

This paper reports on research conducted on the use of priority dispatching rules in a hybrid assembly/job shop which manufactures both single-component and multiple-component products. A simulation model was constructed and a large stale experiment performed. Statistical analysis of the simulation results indicated significant impact of both the priority rules tested, and the product-mix considered on shop performance.

Among the 12 priority rules tested, the SPT (shortest processing time) rule and the ASMF-SPT (assembly jobs first with SPT as tie-breaker) rule performed very well with respect to measures like lateness, flow time, tardiness, staging time, and percent of jobs tardy. These findings lead to further investigation of a combined priority rule, MIXED, which implements the ASMF-SPT rule at all machine centres that process components of assembly jobs, and the SPT rule at the remaining machine centres which process non-component jobs. The additional research results yielded evidence that the MIXED rule can reduce the staging time of the SPT rule, and yielded betrer results than the ASMF-SPT rule with regard to other performance measures.

The most interesting finding, however, was the small variation in flow time distribution resulting from use of the MIXED rule when there were more assembly jobs. In an MRP environment, it is especially desirable to have a priority dispatching rule resulting in minimum variation in individual flow times which allows the replenishment lead times to be estimated with greater accuracy.     

Order release in a workload controlled flow-shop with sequence-dependent set-up times

In this paper, we report a simulation study on the role of sequence-dependent set-up times in decision making at the order release level of a workload controlled make-to-order flow-shop. The study evaluates the potential for set-ups savings, dependent on the level of workload in the shop, for two alternative strategies, namely considering set-up times centrally, within the release decision or locally, within the dispatching decision. These strategies are compared and assessed on the basis of two main performance measures namely time in system and standard deviation of the job lateness. Results indicate that the local strategy, which has been traditionally adopted in practice and in most of the studies dealing with sequence-dependent set-up times, does not always give the best results. The release frequency and the shop workload appear critical to the selection of the strategy to adopt, strongly influencing system performance.     

Impact of sequence-dependent setup time on job shop scheduling performance

In a production system using multi-purpose and flexible machines, reducing setup time is an important task for better shop performance. Numerous cases were reported about successful reduction of setup times by standardization of setup procedures. However, setup times have not been eliminated and remain an important element of real production problems for production systems such as commercial printing, plastics manufacturing, metal processing, etc. It is especially critical when the setup time is sequence dependent. In this situation, shop performance cannot be effectively improved without the aid of an appropriate scheduling procedure. Review of the past studies shows that there has not been a significant amount of research done on the scheduling procedure for a dynamic job shop with sequence dependent setup times. This paper investigates the job shop scheduling problems that are complicated by sequence-dependent setup times. The study classifies and tests scheduling rules by considering whether setup time and/or due date information is employed. These scheduling rules are evaluated in dynamic scheduling environments defined by due date tightness, setup times and cost structure. A simulation model of a nine machine job shop is used for the experiment. A hypothetical, asymmetric, setup time matrix is applied to the nine machines.     

Due Date Assignment in a Multistage Job Shop

In a Materials Requirements Planning (MRP) system, component lead times are generally assumed to be known and constant. Since a requirement of a MRP system is that components finish on time, slack is often built into component lead times to insure that actual job flowtimes equal planned job lead times. In this study, job characteristics and shop characteristics are investigated to determine which has a greater impact on predicting job flowtimes. This is accomplished by determining which characteristic most greatly influences the deviation of planned job lead times from actual job flowtimes. After identifying those factors which have the greatest influence on the job's flowtime, due date assignment rules are developed. A simulation study is then made to determine. which of the due date assignment rules perform best for varying product structures, as defined by various Bills of Materials (BOMs), and various shop conditions. Simulation test results are presented and discussed.     

Quantum-inspired ant colony optimisation algorithm for a two-stage permutation flow shop with batch processing machines

This paper studied two-stage permutation flow shop problems with batch processing machines, considering different job sizes and arbitrary arrival times, with the optimisation objective of minimising the makespan. The quantum-inspired ant colony optimisation (QIACO) algorithm was proposed to solve the problem. In the QIACO algorithm, the ants are divided into two groups: one group selects the largest job in terms of job size as the initial job for each batch and the other group selects the smallest job as the initial job for each batch. Each group of ants has its own pheromone matrix. In the computational experiment, our novel algorithm was compared with the hybrid discrete differential evolution (HDDE) algorithm and the batch-based hybrid ant colony optimisation (BHACO) algorithm. Although the HDDE algorithm has a shorter run time, the quality of the solution for large-scale jobs is not good, while the BHACO algorithm always obtains a better solution but requires a longer run time. The computational results show that the QIACO algorithm embedded in the quantum information has advantages in terms of both solution quality and running time.     

A priority scheduling approach for flexible job shops with multiple process plans

This paper considers the job shop scheduling problem with alternative operations and machines, called the flexible job shop scheduling problem. As an extension of previous studies, operation and routing flexibilities are considered at the same time in the form of multiple process plans, i.e. each job can be processed through alternative operations, each of which can be processed on alternative machines. The main decisions are: (a) selecting operation/machine pair; and (b) sequencing the jobs assigned to each machine. Since the problem is highly complicated, we suggest a practical priority scheduling approach in which the two decisions are done at the same time using a combination of operation/machine selection and job sequencing rules. The performance measures used are minimising makespan, total flow time, mean tardiness, the number of tardy jobs, and the maximum tardiness. To compare the performances of various rule combinations, simulation experiments were done on the data for hybrid systems with an advanced reconfigurable manufacturing system and a conventional legacy system, and the results are reported.