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.     

Novel slack-based robust scheduling rule for a semiconductor manufacturing system with uncertain processing time

The NP-hard scheduling problems of semiconductor manufacturing systems (SMSs) are further complicated by stochastic uncertainties. Reactive scheduling is a common dynamic scheduling approach where the scheduling scheme is refreshed in response to real-time uncertainties. The scheduling scheme is overly sensitive to the emergence of uncertainties because the optimization of performance (such as minimum make-span) and the system robustness cannot be achieved simultaneously by conventional reactive scheduling methods. To improve the robustness of the scheduling scheme, we propose a novel slack-based robust scheduling rule (SR) based on the analysis of robustness measurement for SMS with uncertain processing time. The decision in the SR is made in real time given the robustness. The proposed SR is verified under different scenarios, and the results are compared with the existing heuristic rules. Simulation results show that the proposed SR can effectively improve the robustness of the scheduling scheme with a slight performance loss.     

Performance evaluation of dynamic scheduling approaches in vehicle-based internal transport systems

This paper studies the performance of static and dynamic scheduling approaches in vehicle-based internal transport (VBIT) systems and is one of the first to systematically investigate under which circumstances, which scheduling method helps in improving performance. In practice, usually myopic dispatching heuristics are used, often using look-ahead information. We argue more advanced scheduling methods can help, depending on circumstances. We introduce three basic scheduling approaches (insertion, combined and column generation) for the static problem. We then extend these to a dynamic, real-time setting with rolling horizons. We propose two further real-time scheduling approaches: dynamic assignment with and without look-ahead. The performances of the above five scheduling approaches are compared with two of the best performing look-ahead dispatching rules known from the literature. The performance of the various approaches depends on the facility layout and work distribution. However, column generation, the combined heuristic, and the assignment approach with look-ahead consistently outperform dispatching rules. Column generation can require substantial calculation time but delivers very good performance if sufficient look-ahead information is available. For large scale systems, the combined heuristic and the dynamic assignment approach with look ahead are recommended and have acceptable calculation times.     

Makespan minimisation for a parallel machine scheduling problem with preemption and job incompatibility

In this paper, an extension of the graph colouring problem is introduced to model a parallel machine scheduling problem with job incompatibility. To get closer to real-world applications, where the number of machines is limited and jobs have different processing times, each vertex of the graph requires multiple colours and the number of vertices with the same colour is bounded. In addition, several objectives related to scheduling are considered: makespan, number of pre-emptions and summation over the jobs’ throughput times. Different solution methods are proposed, namely, two greedy heuristics, two tabu search methods and an adaptive memory algorithm. The latter uses multiple recombination operators, each one being designed for optimising a subset of objectives. The most appropriate operator is selected dynamically at each iteration, depending on its past performance. Experiments show that the proposed algorithm is effective and robust, while providing high-quality solutions on benchmark instances for the graph multi-colouring problem, a simplification of the considered problem.     

蚁群系统结合指派规则求解HFS调度问题

以NP-难的最小化时间表长为目标的混合流水车间调度问题为研究对象。把工件在第1阶段开始加工的排序问题转化为旅行商问题,采用蚁群系统求得初始排序;在第1阶段后各阶段采用工件先到先服务规则选择工件、最先空闲机器优先规则选择机器以构建初始工件的机器指派与排序;充分利用已知的机器布局和工件加工时间特点,确定工件加工瓶颈阶段,并以此为基础对工件的机器指派与排序进行改进。用Carlier和Neron设计的Benchmark算例仿真后与著名的NEH算法比较,表明这种算法是有效的。     

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.     

Robust scheduling of a two-machine flow shop with uncertain processing times

This paper focuses on manufacturing environments where job processing times are uncertain. In these settings, scheduling decision makers are exposed to the risk that an optimal schedule with respect to a deterministic or stochastic model will perform poorly when evaluated relative to actual processing times. Since the quality of scheduling decisions is frequently judged as if processing times were known a priori, robust scheduling, i.e., determining a schedule whose performance (compared to the associated optimal schedule) is relatively insensitive to the potential realizations of job processing times, provides a reasonable mechanism for hedging against the prevailing processing time uncertainty. In this paper we focus on a two-machine flow shop environment in which the processing times of jobs are uncertain and the performance measure of interest is system makespan. We present a measure of schedule robustness that explicitly considers the risk of poor system performance over all potential realizations of job processing times. We discuss two alternative frameworks for structuring processing time uncertainty. For each case, we define the robust scheduling problem, establish problem complexity, discuss properties of robust schedules, and develop exact and heuristic solution approaches. Computational results indicate that robust schedules provide effective hedges against processing time uncertainty while maintaining excellent expected makespan performance     

A coloured Petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles

To achieve a significant improvement in the overall performance of a flexible manufacturing system, the scheduling process must consider the interdependencies that exist between the machining and transport systems. However, most works have addressed the scheduling problem as two independent decision making problems, assuming sufficient capacity in the transport system. In this paper, we study the simultaneous scheduling (SS) problem of machines and automated guided vehicles using a timed coloured Petri net (TCPN) approach under two performance objectives; makespan and exit time of the last job. The modelling approach allows the evaluation of all the feasible vehicle assignments as opposed to the traditional dispatching rules and demonstrates the benefits of vehicle-controlled assignments over machine-controlled for certain production scenarios. In contrast with the hierarchical decomposition technique of existing approaches, TCPN is capable of describing the dynamics and evaluating the performance of the SS problem in a single model. Based on TCPN modelling, SS is performed using a hybrid heuristic search algorithm to find optimal or near-optimal schedules by searching through the reachability graph of the TCPN with heuristic functions. Large-sized instances are solved in relatively short computation times, which were a priori unsolvable with conventional search algorithms. The algorithm’s performance is evaluated on a benchmark of 82 test problems. Experimental results indicate that the proposed algorithm performs better than the conventional ones and compares favourably with other approaches.     

Experimental investigation of flexible manufacturing system scheduling decision rules

This paper reports the results of an experimental investigation of scheduling decision rules for a dedicated flexible manufacturing system. A simulation model of an existing flexible manufacturing system (FMS) comprised of 16 computer numerical controlled machines (CNC) was constructed using actual operation routings and machining times to evaluate the performance of various part loading and routing procedures. The results indicate that FMS performance is significantly affected by the choice of heuristic parts scheduling rules.     

β-Robust scheduling for single-machine systems with uncertain processing times

In scheduling environments with processing time uncertainty, system performance is determined by both the sequence in which jobs are ordered and the actual processing times of jobs. For these situations, the risk of achieving substandard system performance can be an important measure of scheduling effectiveness. To hedge this risk requires an explicit consideration of both the mean and the variance of system performance associated with alternative schedules, and motivates a β-robustness objective to capture the likelihood that a schedule yields actual performance no worse than a given target level. In this paper we focus on β-robust scheduling issues in single-stage production environments with uncertain processing times. We define a general β-robust scheduling objective, formulate the β-robust scheduling problem that results when job processing times are independent random variables and the performance measure of interest is the total flow time across all jobs, establish problem complexity, and develop exact and heuristic solution approaches. We then extend the 0-robust scheduling model to consider situations where the uncertainty associated with individual job processing times can be selectively controlled through resource allocation. Computational results are reported to demonstrate the efficiency and effectiveness of the solution procedures.     

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.     

An effective heuristic for scheduling a yard crane to handle jobs with different ready times

In land-constrained port container terminals, yard cranes are commonly used for handling containers in a container yard to load containers onto or unload containers from trucks. However, yard cranes are bulky, slow and need to move frequently between their work locations. As it is common that the container flow in a terminal is bottlenecked by yard crane operations, effective work schedules of yard cranes are needed to increase the terminal’s throughput. This article studies the problem of scheduling a yard crane to perform a given set of container handling jobs with different ready times. The objective is to minimize the sum of job waiting times. It is noted that the scheduling problem is NP-complete. This research develops a heuristic to solve the scheduling problem and an algorithm to find lower bounds for benchmarking the schedules found by the heuristic. The performance of the heuristic is evaluated by a set of test problems generated on the basis of real-life terminal operations data. Indeed, the computational results show that the proposed heuristic can find effective solutions for the scheduling problem.     

Scheduling a dynamic flexible flow line with sequence-dependent setup times: a simulation analysis

This paper presents a simulation-based experimental study of scheduling rules for scheduling a dynamic flexible flow line problem considering sequence-dependent setup times. A discrete-event simulation model is presented as well as eight adapted heuristic algorithms, including seven dispatching rules and one constructive heuristic, from the literature. In addition, six new proposed heuristics are implemented in the simulation model. Simulation experiments are conducted under various conditions such as setup time ratio and shop utilisation percentage. One of the proposed rules performs better for the mean flow time measure and another one performs better for the mean tardiness measure. Finally, multiple linear regression based meta-models are developed for the best performing scheduling rules.     

Single CNC machine scheduling with controllable processing times and multiple due dates

In this study, we solve the single CNC machine scheduling problem with controllable processing times. Our objective is to maximize the total profit that is composed of the revenue generated by the set of scheduled jobs minus the sum of total weighted earliness and weighted tardiness, tooling and machining costs. Customers offer multiple due dates to the manufacturer, each coming with a distinct price for the order that is decreasing as the date gets later, and the manufacturer has the flexibility to accept or reject the orders. We propose a number of ranking rules and scheduling algorithms that we employ in a four-stage heuristic algorithm that determines the processing times for each job and a final schedule for the accepted jobs simultaneously, to maximize the overall profit.     

Forecasting policies for scheduling a stochastic due date job shop

This work studies the problem of scheduling a production plant subject to uncertain processing times that may arise, e.g. from the variability of human labour or the possibility of machine breakdowns. The problem is modelled as a job shop with random processing times, where the expected total weighted tardiness must be minimized. A heuristic is proposed that amplifies the expected processing times by a selected factor, which are used as input for a deterministic scheduling algorithm. The quality of a particular solution is measured using a risk averse penalty function combining the expected deviation and the worst case deviation from the optimal schedule. Computational tests show that the technique improves the performance of the deterministic algorithm by 25% when compared with using the unscaled expected processing times as inputs.     

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

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

A dynamic scheduling algorithm for singe-arm two-cluster tools with flexible processing times

This article presents a dynamic algorithm for job scheduling in two-cluster tools producing multi-type wafers with flexible processing times. Flexible processing times mean that the actual times for processing wafers should be within given time intervals. The objective of the work is to minimize the completion time of the newly inserted wafer. To deal with this issue, a two-cluster tool is decomposed into three reduced single-cluster tools (RCTs) in a series based on a decomposition approach proposed in this article. For each single-cluster tool, a dynamic scheduling algorithm based on temporal constraints is developed to schedule the newly inserted wafer. Three experiments have been carried out to test the dynamic scheduling algorithm proposed, comparing with the results the ‘earliest starting time’ heuristic (EST) adopted in previous literature. The results show that the dynamic algorithm proposed in this article is effective and practical.     

Intelligent scheduling of discrete automated production line via deep reinforcement learning

The reinforcement learning (RL) is being used for scheduling to improve the adaptability and flexibility of an automated production line. However, the existing methods only consider processing time certain and known and ignore production line layouts and transfer unit, such as robots. This paper introduces deep RL to schedule an automated production line, avoiding manually extracted features and overcoming the lack of structured data sets. Firstly, we present a state modelling method in discrete automated production lines, which is suitable for linear, parallel and re-entrant production lines of multiple processing units. Secondly, we propose an intelligent scheduling algorithm based on deep RL for scheduling automated production lines. The algorithm establishes a discrete-event simulation environment for deep RL, solving the confliction of advancing transferring time and the most recent event time. Finally, we apply the intelligent scheduling algorithm into scheduling linear, parallel and re-entrant automated production lines. The experiment shows that our scheduling strategy can achieve competitive performance to the heuristic scheduling methods and maintains stable convergence and robustness under processing time randomness.     

A heuristic model for dynamic flexible job shop scheduling problem considering variable processing times

In real scheduling problems, unexpected changes may occur frequently such as changes in task features. These changes cause deviation from primary scheduling. In this article, a heuristic model, inspired from Artificial Bee Colony algorithm, is proposed for a dynamic flexible job-shop scheduling (DFJSP) problem. This problem consists of n jobs that should be processed by m machines and the processing time of jobs deviates from estimated times. The objective is near-optimal scheduling after any change in tasks in order to minimise the maximal completion time (Makespan). In the proposed model, first, scheduling is done according to the estimated processing times and then re-scheduling is performed after determining the exact ones considering machine set-up. In order to evaluate the performance of the proposed model, some numerical experiments are designed in small, medium and large sizes in different levels of changes in processing times and statistical results illustrate the efficiency of the proposed algorithm.     

Capacity-constrained scheduling for a logic IC final test facility

A capacity-constrained scheduling using the concept of the theory of constraints for a semiconductor Logic IC final test operation is presented. The scheduling of the IC final test considers unrelated parallel machines with multiple constraint problems. A broad product mix, variable lot sizes and yields, long and variable set-up times, as well as limited test equipment capacity characterize the operations in this test facility. Discrete event simulation models based on e-M-Plant? are developed to implement the capacity-constrained scheduling algorithm. A comparison is also made with other rules, which are combinations of the rules such as first come first serve and earliest due date for the order scheduling, and the rules such as minimum set-up time, shortest processing time and shortest set-up time plus processing time for the dispatching test equipment. The simulation results show that the proposed capacity-constrained scheduling outperforms other rules for the committed volume performance in many different operational conditions. Directions for future research are also presented.