On-line scheduling of multi-server batch operations

The batching of jobs in a manufacturing system is a very common policy in many industries. The main reasons for batching are the avoidance of setups and/or facilitation of material handling. Good examples of batch-wise production systems are the ovens that are found in the aircraft industry and in the manufacture of semiconductors. These systems often consist of multiple machines of different types for the range and volumes of products that have to be handled. Building on earlier research in the aircraft industry, where the process of hardening synthetic aircraft parts was studied, we propose a new heuristic for the dynamic scheduling of these types of systems. Our so-called look-ahead strategy bases its decision to schedule a job on a certain machine on the availability of information on a limited number of near future arrivals. The new control strategy distinguishes itself from existing heuristics by an integrated approach that involves all machines in the scheduling decision, instead of only considering idle machines. It is shown by an extensive series of simulation experiments that the new heuristic outperforms existing heuristics for most system configurations. Especially in the case of complex systems, where multiple products have to be handled by non-identical machines, the new heuristic proves its value as a practical scheduling tool. Important insight is obtained with regard to the relation between the system is configuration and its performance.     

Minimizing makespan in a two-stage flow shop with parallel batch-processing machines and re-entrant jobs

Against a background of heat-treatment operations in mould manufacturing, a two-stage flow-shop scheduling problem is described for minimizing makespan with parallel batch-processing machines and re-entrant jobs. The weights and release dates of jobs are non-identical, but job processing times are equal. A mixed-integer linear programming model is developed and tested with small-scale scenarios. Given that the problem is NP hard, three heuristic construction methods with polynomial complexity are proposed. The worst case of the new constructive heuristic is analysed in detail. A method for computing lower bounds is proposed to test heuristic performance. Heuristic efficiency is tested with sets of scenarios. Compared with the two improved heuristics, the performance of the new constructive heuristic is superior.     

Adaptive scheduling of batch servers in flow shops

Batch servicing is a common way of benefiting from economies of scale in manufacturing operations. Good examples of production systems that allow for batch processing are ovens found in the aircraft industry and in semiconductor manufacturing. In this paper we study the issue of dynamic scheduling of such systems within the context of multi-stage flow shops. So far, a great deal of research has concentrated on the development of control strategies, which only address the batch stage. This paper proposes an integral scheduling approach that also includes succeeding stages. In this way, we aim for shop optimization, instead of optimizing performance for a single stage. Our so-called look-ahead strategy adapts its scheduling decision to shop status, which includes information on a limited number of near-future arrivals. In particular, we study a two-stage flow shop, in which the batch stage is succeeded by a serial stage. The serial stage may be realized by a single machine or by parallel machines. Through an extensive simulation study it is demonstrated how shop performance can be improved by the proposed strategy relative to existing strategies.     

Dynamic control of the batch processor in a serial-batch processor system with mean tardiness performance

Effective control of batch processors is very essential to improve on-time delivery of wafers in semiconductor manufacturing. In this paper, the focus is on mean tardiness performance of a batch processor in a two-stage processor system by including an upstream serial processor. Two new control strategies are proposed for this problem. The first strategy effectively incorporates the product information at the upstream serial station in batching decisions. The second strategy further applies a re-sequencing approach in the serial processor's queue when there is a benefit in shortening the arrival time of an urgent product. Discrete event simulation is used to test the performance of the strategies. Results are very promising as compared to benchmark control strategies.     

Minimising makespan on a single batch processing machine with dynamic job arrivals and non-identical job sizes

Batch scheduling is a prevalent policy in many industries such as burn-in operations in semiconductor manufacturing and heat treatment operations in metalworking. In this paper, we consider the problem of minimising makespan on a single batch processing machine in the presence of dynamic job arrivals and non-identical job sizes. The problem under study is NP-hard. Consequently, we develop a number of efficient construction heuristics. The performance of the proposed heuristics is evaluated by comparing their results to two lower bounds, and other solution approaches published in the literature, namely the first-fit longest processing time-earliest release time (FFLPT-ERT) heuristic, hybrid genetic algorithm (HGA), joint genetic algorithm and dynamic programming (GA+DP) approach and ant colony optimisation (ACO) algorithm. The computational experiments demonstrate the superiority of the proposed heuristics with respect to solution quality, especially for the problems with small size jobs. Moreover, the computational costs of the proposed heuristics are very low.     

Scheduling a batch processing machine with non-identical job sizes: a clustering perspective

Batch processing machines that process a group of jobs simultaneously are often encountered in semiconductor manufacturing and metal heat treatment. This paper considered the problem of scheduling a batch processing machine from a clustering perspective. We first demonstrated that minimising makespan on a single batching machine with non-identical job sizes can be regarded as a special clustering problem, providing a novel insight into scheduling with batching. The definition of WRB (waste ratio of batch) was then presented, and the objective function of minimising makespan was transformed into minimising weighted WRB so as to define the distance measure between batches in a more understandable way. The equivalence of the two objective functions was also proved. In addition, a clustering algorithm CACB (constrained agglomerative clustering of batches) was proposed based on the definition of WRB. To test the effectiveness of the proposed algorithm, the results obtained from CACB were compared with those from the previous methods, including BFLPT (best-fit longest processing time) heuristic and GA (genetic algorithm). CACB outperforms BFLPT and GA especially for large-scale problems.     

Decision-making on multi-mould maintenance in production scheduling

The reliability of a critical tool like a mould on a machine affects the productivity seriously in many manufacturing firms. In fact, its breakdown frequency is even higher than machines. The decision-making on when mould maintenance should be started become a challenging issue. In the previous study, the mould maintenance plans were integrated with the traditional production schedules in a plastics production system. It was proven that considering machine and mould maintenance in production scheduling could improve the overall reliability and productivity of the production system. However, the previous model assumed that each job contained single operation. It is not workable in other manufacturing systems such as die stamping which may contain multiple operations with multiple moulds in each job. Thus, this study models a new problem for multi-mould production-maintenance scheduling. A genetic algorithm approach is applied to minimise the makespan of all jobs in 10 hypothetical problem sets. A joint scheduling (JS) approach is proposed to decide the start times of maintenance activities during scheduling. The numerical result shows that the JS approach has a good performance in the new problem and it is sensitive to the characteristic of the setup time defined.     

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.     

Scheduling pickup and deliveries in a multiple-load discrete carrier environment

The importance and benefits of using multiple-load carriers in advanced manufacturing systems has been well documented in recent studies. This study assumes a manufacturing system arranged around a single loop serviced by a single multiple-load carrier. The study presents a {0-1} integer programming model for optimal schedule design, if complete knowledge is available, using a finite planning horizon. In order to solve larger dynamic problems where jobs keep on arriving, two heuristic algorithms are developed, each using a different look-ahead period. The ability of these algorithms is analyzed and compared to the simple First-Encountered-First-Served (FEFS) rule using 31 randomly generated problems. Finally, the impact of increasing carrier capacity is studied.     

Dynamic scheduling of batch servers with compatible product families

Dynamic scheduling is considered for batch processing machines. Research is motivated by the burn-in ovens found in semiconductor manufacturing. So far, research in this field has concentrated on control strategies that assume batches to be homogeneous, i.e. products should all belong to the same family. However, burn-in ovens may allow simultaneous processing of alternative families of products. Each family may set different requirements to processing times. The processing time of a batch is equal to the longest processing time required among all products in the batch. A new scheduling approach is proposed that addresses these situations. The objective is to minimize average flow time per product for the batch operation. The so-called look-ahead strategy adapts its scheduling decision to shop status, which includes information on a limited number of near future arrivals. The potential of the new strategy is demonstrated by an extensive simulation study.     

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.     

A genetic algorithm approach for production scheduling with mould maintenance consideration

The traditional approach for maintenance scheduling concerns single-resource (machine) maintenance during production which may not be sufficient to improve production system reliability as a whole. Besides, in the literature many researchers schedule maintenance activities periodically with fixed maintenance duration. However, in a real manufacturing system maintenance activities can be executed earlier and the maintenance duration will become shorter since less time and effort are required. A practical example is that in a plastic production system, the proportion of machine-related downtime is even lower than mould-related downtime. The planned production operations are usually interrupted seriously because of the mismatch among the maintenance periods between injection machine and mould. In this connection, this paper proposes to jointly schedule production and maintenance tasks of multi-resources in order to improve production system reliability by reducing the mismatch among various processes. To integrate machine and mould maintenance tasks in production, this paper attempts to model the production scheduling with mould scheduling (PS-MS) problem with time-dependent deteriorating maintenance schemes. The objective of this paper is to propose a genetic algorithm approach to schedule maintenance tasks jointly with production jobs for the PS-MS problem, so as to minimise the makespan of production jobs.     

Heuristic algorithms for scheduling heat-treatment furnaces of steel casting industries

This paper addresses a research problem of scheduling parallel, non-identical batch processors in the presence of dynamic job arrivals, incompatible job-families and non-identical job sizes. We were led to this problem through a real-world application involving the scheduling of heat-treatment operations of steel casting. The scheduling of furnaces for heat-treatment of castings is of considerable interest as a large proportion of the total production time is the processing times of these operations. In view of the computational intractability of this type of problem, a few heuristic algorithms have been designed for maximizing the utilization of heat-treatment furnaces of steel casting manufacturing. Extensive computational experiments were carried out to compare the performance of the heuristics with the estimated optimal value (using the Weibull technique) and for relative effectiveness among the heuristics. Further, the computational experiments show that the heuristic algorithms proposed in this paper are capable of obtaining near (statistically estimated) optimal utilization of heat-treatment furnaces and are also capable of solving any large size real-life problems with a relatively low computational effort.     

Sequential tolerance control in discrete parts manufacturing

The machining of complex parts typically involves a logical and chronological sequence of n operations on m machine tools. Because manufacturing datums cannot always match design datums, some of the design specifications imposed on the part are usually satisfied by distinct subsets of the n operations prescribed in the process plan. Conventional tolerance control specifies a fixed set point for each operation and permissible variation about this set point to insure compliance with the specifications. This approach is inadequate for complex, low volume, highvalue added parts such as those found in the aircraft, nuclear, or precision instrument manufacturing industry. This paper introduces the concept of Sequential Tolerance Control, an approach that uses real-time measurement information at the completion of stage j to exploit available space inside a dynamic feasible zone and reposition the set point for operations j + 1 to n. The procedure is repeated at appropriate locations along the n operations so as to optimize the production of an acceptable part.     

Evaluating order throughput time with variable time window batching

Given increased pressure to provide short delivery times, minimising customer order throughput time is a very important objective in warehousing operations. There are many factors that may affect the performance of an order picking system, such as layout of the warehouse, the storage strategy, the routing policy, the zoning method and the batching policy. In this study, we propose a simple travel time model and analyse the effect of order batching on the expected customer order throughput time with variable time window batching. In addition, we discussed the impact of some parameters on the batch size and the expected customer order throughput time. In the practice of Wuhan Dong Hon Logistics co. Ltd, the storage rack in the warehouse has two levels: the low storage level and the high storage level. These two levels are visited by pickers and forklifts, respectively. The classification improves the performance of order picking. In this study, we build the model based on this practice.     

供应链伙伴关系、信息共享与企业运营绩效关系

本文以广东省珠三角地区制造企业为调查对象,对供应链伙伴关系、信息共享与企业运营绩效之间关系进行研究.研究结果表明,供应链伙伴关系对信息共享存在显著的正向影响,即增强供应链伙伴关系将有助于提高企业之间信息共享水平;信息共享对企业运营绩效存在显著的正向影响;供应链伙伴关系不仅直接影响企业运营绩效,而且通过信息共享间接地影响到企业运营绩效.另外,我们还发现在供应链伙伴关系中的信任对信息共享与企业运营绩效均有非常显著的影响.本文研究结论可为我国制造企业实施供应链管理策略提供理论指导.     

JOB ASSIGNMENT ALGORITHMS ON UNIFORM PARALLEL MACHINES

Uniform parallel machine scheduling problems with a makespan measure cannot generally be solved within polynomial time complexity. This paper considers special problems with a single type of job on the uniform parallel machines, where each machine is available at a given ready time. Also the machine can be restricted on the number of jobs to be processed. The objective is to develop job assignment or batching algorithms which minimize makespan. When all the machines are available at time zero and have no restriction on the number of assignable jobs, a lower bound and optimal solution properties are derived. Based upon these properties, a polynomial algorithm is suggested to find the optimal job assignment on each machine. Three generalized problems are considered under the following situations: (1) some machines have capacity restrictions on the production batch, (2) each machine has its ready time, and (3) the jobs require series-parallel operations. The generalized problems arc also characterized and polynomial algorithms are developed for the same aim of optimal job assignment, except for the case of series-parallel operations. A heuristic algorithm is suggested with numerical tests for the series-parallel operations problem     

Assess the effects of different operations policies on warehousing reliability

In this study, an assessment model for analysing the reliability of a warehouse system, focusing on resource capability, under given combinations of storage, routing, batching and zoning process policies, is proposed. A reliability assessment model is developed in order to evaluate the effect of different combinations of operations policies on warehouse reliability. To better reflect the real order pick up operations at the warehouse, a simulation model based on the operation scenarios of a Hong Kong logistics service company is developed. The simulation results are used for supporting the evaluation of warehouse reliability through using the proposed reliability assessment model. The most important finding indicates that order batching together with zoning policies yields greater warehouse reliability particularly when the daily order volume is large. In addition, another important research finding shows that warehouse performance is not constant and can drop when certain combinations of operations policies are adopted. The degrading rate of the resource (forklift) when used according to a given combination of polices is also defined by the proposed assessment method. Hence, the result helps logistics service providers enhance resource durability through modifying operations policies and by implementing proper preventive maintenance policies within a dynamic operations environment.     

A comparative evaluation of sequential set point adjustment procedures for tolerance control

The machining of complex parts typically involves a logical and chronological sequence of n operations on m machine tools. Because manufacturing datums cannot always match design datums, some of the design specifications imposed on the part are usually satisfied by distinct subsets of the n operations prescribed in the process plan. Conventional tolerance control specifies a fixed set point for each operation and permissible variation about this set point to insure compliance with the specifications. Sequential tolerance control (STC) uses real-time measurement information at the completion of one stage to exploit the available space inside a dynamic feasible zone and reposition the set point for subsequent operations. This paper introduces an extension of STC that utilizes the variability of the operations to scale the problem data and further enhance the ability of STC to optimize the production of an acceptable part.     

Dynamic order batching in bucket brigade order picking systems with consecutive batch windows and non-identical pickers

The blocking mitigation mechanism contained in a batching and sequencing model improves order picking performance in bucket brigade order picking systems by adjusting the batch formation in a given batch window. The batch formation of a given batch window affects the transition to the next batch window and limits the batch formation’s structure in the next window. In addition, imbalance in picker capability increases the variation of batch formation while mitigating blocking delay. Our paper proposes a dynamic indexed batching model to smooth the transition between consecutive batch windows and give a better approximation of non-identical pickers’ capability. We develop a mixed integer programming solution for a dynamic indexed batching model in a bucket brigade order picking system (DIBMB). Simulation experiments show that the DIBMB smooths the transition between batch windows as measured in the delay experienced by the first batch in each batch window. Comparisons to the available batching models show that under DIBMB, the blocking delay gradually increases throughout the sequence of batches.