A novel timetabling algorithm for a furnace process for semiconductor fabrication with constrained waiting and frequency-based setups

This study aims to solve the scheduling problem arising from oxide–nitride–oxide (ONO) stacked film fabrication in semiconductor manufacturing. This problem is characterized by waiting time constraints, frequency-based setups, and capacity preoccupation. To the best of our knowledge, none of the existing studies has addressed constrained waiting time and frequency-based setups at the same time. To fill this gap, this study develops a genetic algorithm for batch sequencing combined with a novel timetabling algorithm. For validation, we conducted several experiments based on empirical data. As a benchmark for small-sized problem instances, a mixed-integer linear programming model was used. The results show that the proposed algorithm optimally solves most cases of the ONO scheduling problem in real settings and significantly outperforms dispatching rule-based heuristics.     

Scheduling Multi-Mode Resource-Constrained Projects Using Heuristic Rules Under Uncertainty Environment

Project scheduling is a key objective of many models and is the proposed method for project planning and management. Project scheduling problems depend on precedence relationships and resource constraints, in addition to some other limitations for achieving a subset of goals. Project scheduling problems are dependent on many limitations, including limitations of precedence relationships, resource constraints, and some other limitations for achieving a subset of goals. Deterministic project scheduling models consider all information about the scheduling problem such as activity durations and precedence relationships information resources available and required, which are known and stable during the implementation process. The concept of deterministic project scheduling conflicts with real situations, in which in many cases, some data on the activity' s durations of the project and the degree of availability of resources change or may have different modes and strategies during the process of project implementation for dealing with multi-mode conditions surrounded by projects and their activity durations. Scheduling the multi-mode resource-constrained project problem is an optimization problem whose minimum project duration subject to the availability of resources is of particular interest to us. We use the multi-mode resource allocation and scheduling model that takes into account the dynamicity features of all parameters, that is, the scheduling process must be flexible to dynamic environment features. In this paper, we propose five priority heuristic rules for scheduling multi-mode resource-constrained projects under dynamicity features for more realistic situations, in which we apply the proposed heuristic rules (PHR) for scheduling multi-mode resource-constrained projects. Five projects are considered test problems for the PHR. The obtained results rendered by these priority rules for the test problems are compared by the results obtained from 10 well-known heuristics rules rendered for the same test problems. The results in many cases of the proposed priority rules are very promising, where they achieve better scheduling dates in many test case problems and the same results for the others. The proposed model is based on the dynamic features for project topography.     

Minimizing makespan on parallel machines with release time and machine eligibility restrictions

Scheduling in the presence of machine eligibility restrictions when not all machines can process all the jobs is a practical problem into which there has been little research. Pinedo demonstrated that the least flexible job (LFJ) rule was optimal for minimizing makespan in a parallel machine environment (with equal processing times) when there are machine eligibility restrictions, the machine eligibility sets are nested, and no release time constraint exists. The results presented in this paper demonstrate that for the more realistic case when the machine eligibility sets are not nested (with unequal processing times known when a job is released), the longest processing time (LPT) rule performs better than the LFJ rule in the presence or absence of release time stipulations. The experimental results show that the order (job selection first or machine selection first) does not matter, which is consistent with Pinedo’s observation. The new heuristics that are evaluated in this paper provide important results for the parallel machine scheduling problem and their applications in the semiconductor industry, which motivated this research.     

Scheduling direct deliveries with time windows to minimise truck fleet size and customer waiting times

This paper tackles the operational problem of scheduling direct deliveries from a single source (e.g. a distribution centre) to multiple customers (e.g. assembly plants). The problem consists of scheduling a set of given round trips such that each trip is processed exactly once within its time window and the employed truck fleet is as small as possible. Moreover, as a secondary objective, customer waiting times should be minimal. Such planning problems arise in many industries like, for instance, the automotive industry, where just-in-time parts are often shipped via direct delivery to OEMs. We propose two different mixed-integer programming models for this problem, discuss similarities to classic routing and scheduling problems from the literature, identify a subproblem that is solvable in polynomial time and propose suitable heuristics. In a computational study, the proposed procedures are shown to perform well both on newly generated instances as well as those from the literature. We also show that minimising waiting times is an adequate measure to make schedules more robust in the face of unforeseen disturbances.     

The no-wait two-machine flow shop scheduling problem with convex resource-dependent processing times

We extend the classical no-wait two-machine flow shop scheduling problem to the case where job-processing times are controllable through the allocation of a common, limited and nonrenewable resource. Our objective is to simultaneously determine the sequence of the jobs and the resource allocation for each job on both machines in order to minimize the makespan. By using the equivalent load method to obtain the optimal resource allocation on a series-parallel graph, we reduce the problem to a sequencing one and show that it is equivalent to a new special case of the Traveling Salesman Problem (TSP). We prove that although the reduced problem forms a subclass of the TSP on permuted Monge matrices, it is still strongly NP-hard. We provide an approximation result and present three special cases which are polynomially solvable. We have also tested two different subtour-patching heuristics in large-scale computational experiments on randomly generated instances of the problem. Both heuristics produced close-to-optimal solutions in most cases.     

Circuit Card Assembly on Tandem Turret-Type Placement Machines

This paper describes a set of heuristics for prescribing the inter-related decisions that form a process plan for assembling a given type of circuit card on a series of turret-type placement machines. Our goals are to prescribe a near-optimal (minimum) cycle time and to do so within a short run time to support process planning. A set of five practical considerations that affect cycle time are addressed. Two sets of test instances are used to evaluate the heuristics, which have polynomial-time complexity. Our tests determine empirically that our heuristics consistently achieve "near-optimal" cycle times and that their run times are bounded by polynomial functions of problem size in the average case.     

Steel-making process scheduling using Lagrangian relaxation

The steel-making process, including steel-making and continuous casting, is usually the bottleneck in iron and steel production. Effective scheduling of this process is thus critical to improve productivity of the entire production system. Unlike the production scheduling in the machinery industry, steel-making process scheduling is characterized by the following features: job grouping and precedence constraints, set-up and removal times on the machines, and high job waiting costs. These features add extra difficulties to the scheduling problem. The objective is to ensure continuity of the production process and just-in-time delivery of final products. In this paper, a novel integer programming formulation with a 'separable' structure is constructed considering all the above-mentioned features. A solution methodology is developed combining Lagrangian relaxation, dynamic programming and heuristics. After relaxing two sets of 'coupling constraints', the relaxed problem is decomposed into smaller subproblems, each involving one job only. These subproblems are solved efficiently by using dynamic programming at the low level while the Lagrangian multipliers are iteratively updated at the high level by using a subgradient method. At the termination of such iterations, a two-stage heuristic is then used to adjust subproblem solutions to obtain a feasible schedule. A numerical experiment demonstrates that the method generates high quality schedules in a timely fashion.     

New scheduling algorithms and digital tool for dynamic permutation flowshop with newly arrived order

The permutation flowshop scheduling problem has been widely studied under static environment by assuming machines and jobs are available at the time of zero. However, in reality, new orders arrive at production systems randomly, which leads to sheer complexity in scheduling due to the dynamic changes given various constraints of resources. Previous studies simply attach new orders directly after the existing schedule. Recent study shows mixing jobs of old and new orders could result in better scheduling solutions. But the heuristic algorithms are still lacking to implement the job mixing policy. To address this problem, a novel scheduling strategy is herein proposed by integrating match-up strategy and real-time strategy (MR) in order to make use of the remaining time before the old order due date. Based on the new MR strategy, eleven new heuristics are introduced with ten existing and one new priority rules. Computational results illustrate the effectiveness of the new heuristics. A digital tool is developed for ease of application of these heuristics, and it is validated by case studies.     

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.     

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.     

面向“货到人”拣选系统的一种随机调度策略

通过“货到人”拣选系统作业流程分析,提出了在分批下发订单任务的情况下的一种随机调度策略。以AGV (automated guided vehicle)完成所有任务的总时间最短为目标函数,以任务分配为决策变量,考虑进行调度时AGV所处的状态以及在完成任务过程中AGV在拣选台的排队等待时间,建立随机调度策略的数学规划模型。利用遗传算法进行求解,通过实例仿真,验证了随机调度策略较调度空闲AGV策略具有更高的拣选效率,同时解决了AGV调度与拣选序列问题,对AGV数量配置具有指导作用。     

Scheduling automated triple cross-over stacking cranes in a container yard

We describe an approach for scheduling triple cross-over stacking cranes in an automated container storage block with asynchronous hand over at the transfer areas at both block front ends. The problem is characterised by frequent long crane moves that make job assignment and crane routing particularly challenging, as an intricate synchronisation between the cranes is required. The main objective is to maximise the productivity of the crane system under peak load while preventing delays in the transport of import and export containers from and to the transfer areas. Our method solves an online optimisation problem by constructing a new crane schedule for a certain planning horizon whenever a new job arrives or a job is completed. We report on extensive simulation studies for evaluating the scheduling strategy. The results show that the method performs significantly better than commonly used heuristics, leading to a productivity gain of more than 20%.     

A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem

As the interest of practitioners and researchers in scheduling in a multi-factory environment is growing, there is an increasing need to provide efficient algorithms for this type of decision problems, characterised by simultaneously addressing the assignment of jobs to different factories/workshops and their subsequent scheduling. Here we address the so-called distributed permutation flowshop scheduling problem, in which a set of jobs has to be scheduled over a number of identical factories, each one with its machines arranged as a flowshop. Several heuristics have been designed for this problem, although there is no direct comparison among them. In this paper, we propose a new heuristic which exploits the specific structure of the problem. The computational experience carried out on a well-known testbed shows that the proposed heuristic outperforms existing state-of-the-art heuristics, being able to obtain better upper bounds for more than one quarter of the problems in the testbed.     

Coordinated scheduling of customer orders with decentralized machine locations

We consider a scheduling model with two machines at different locations. Each job is composed of two tasks where each task must be processed by a specific machine. The finished tasks are shipped to a distribution center in batches before they are bundled together and delivered to customers. The objective is to minimize the sum of the delivery cost and customers' waiting costs. This model attempts to coordinate the production and delivery schedules on the decentralized machines while taking into consideration the shipping cost as well as the waiting time of the customers. We develop polynomial-time heuristic algorithms for this problem and analyze their worst-case performance. Computational experiments are conducted to test the effectiveness of the heuristics and to evaluate the benefits obtained by coordinating the production and delivery of the two decentralized machines.     

Evaluating scheduling heuristics for non-identical parallel processors

Job allocation and job sequencing decisions are combined to develop scheduling heuristics for non-identical parallel processor systems. Several factors affecting the system are examined and the relative performance of the heuristics are evaluated in terms of flow time, tardiness and proportion of tardy jobs. An understanding of the relationship between variables in a scheduling system leads to decision rules that provide feasible and effective production schedules.     

Advanced production scheduling for batch plants in process industries

An Advanced Planning System (APS) offers support at all planning levels along the supply chain while observing limited resources. We consider an APS for process industries (e.g. chemical and pharmaceutical industries) consisting of the modules network design (for long–term decisions), supply network planning (for medium–term decisions), and detailed production scheduling (for short–term decisions). For each module, we outline the decision problem, discuss the specifi cs of process industries, and review state–of–the–art solution approaches. For the module detailed production scheduling, a new solution approach is proposed in the case of batch production, which can solve much larger practical problems than the methods known thus far. The new approach decomposes detailed production scheduling for batch production into batching and batch scheduling. The batching problem converts the primary requirements for products into individual batches, where the work load is to be minimized. We formulate the batching problem as a nonlinear mixed–integer program and transform it into a linear mixed–binary program of moderate size, which can be solved by standard software. The batch scheduling problem allocates the batches to scarce resources such as processing units, workers, and intermediate storage facilities, where some regular objective function like the makespan is to be minimized. The batch scheduling problem is modelled as a resource–constrained project scheduling problem, which can be solved by an efficient truncated branch–and–bound algorithm developed recently. The performance of the new solution procedures for batching and batch scheduling is demonstrated by solving several instances of a case study from process industries.     

越库物流调度问题及其近似与精确算法

在提出问题基础上,建立了基于在制品优化目标的调度模型;根据模型的不同调度特征,给出问题求解的启发式近似算法,并对算法的计算复杂性进行分析,提出问题精确求解的分枝定界算法;通过数值实验验证所给出算法的有效性.表明:分枝定界算法可以有效求解多达40个货物品种的准时制配送问题;启发式算法也具有较高的计算精度,为实际越库物流管理奠定算法基础.     

Critical Ratio Scheduling with Queue Waiting Time Information: An Experimental Analysis

The Critical Ratio and Slack Time priority scheduling rules have been applied by a number of firms in computer-based scheduling systems for manufacturing operations. One question in using these rules is whether queue waiting time estimates for individual machines should be used in making scheduling decisions. Simulation experiments are reported in this paper that measure the effect of including historical queue time data in the Critical Ratio and Slack Time rules. The results suggest that such data can adversely affect shop performance, measured using criteria such as job flow times, job lateness, and inventory system costs.     

Adaptive scheduling in random flexible manufacturing systems subject to machine breakdowns

In a FMS dynamic scheduling environment, frequent rescheduling to react to disruptions such as machine breakdowns can make the behaviour of the system hard to predict, and hence reduce the effectiveness of dynamic scheduling. Another approach to handle the disruptions is to update the job ready time and completion time, and machine status on a rolling horizon basis, and consider the machine availability explicitly in generating schedules. When machine downtime has a small variation, the operation completion time is estimated by using limiting (steady-state) machine availability. However, steady-state analysis is sometimes unlikely to provide a complete picture of the system when there is a large variation in machine downtime and repair time, and frequent disruptions (e.g. tool failures) exist. Transient analysis of machine availability will be more meaningful in such a situation during a finite observation period. In this paper, an adaptive scheduling approach is proposed to make coupled decisions about part/machine scheduling and operation/tool assignments on a rolling horizon basis, while the operation completion time is estimated by a transient machine availability analysis based on a two-state continuous time Markov process. The expected tool waiting time is explicitly considered in the job machine scheduling decision. The effectiveness of the proposed method is compared with other approaches based on various dispatching heuristics such as Apparent Tardiness Cost, Cost OVER Time, and Bottleneck Dynamics, etc under different shop load and machine downtime levels.     

Knowledge-based scheduling in flexible manufacturing systems: An integration of pattern-directed inference and heuristic search

This paper presents a knowledge-based scheduling approach based on the problem-solving techniques developed in artificial intelligence. The approach is based on three key techniques. The first is the pattern-directed inference technique to capture the dynamic nature of the scheduling environment. The second is the non-linear planning technique to coordinate manufacturing processes and resource assignments. The third technique is the A? search algorithm to expedite the searching procedure. It models the scheduling process by state-space transitions; the job routing is obtained through selecting a sequence of scheduling operators guided by heuristics. Keeping track of the manufacturing system by a symbolic world model, this approach is adaptive to such environmental changes as new job arrivals and machine breakdowns, suitable for making real-time scheduling decisions.