A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem

In this paper, we study the job shop scheduling problem with the objective of minimizing the total weighted tardiness. We propose a hybrid shifting bottleneck-tabu search (SB-TS) algorithm by replacing the re-optimization step in the shifting bottleneck (SB) algorithm by a tabu search (TS). In terms of the shifting bottleneck heuristic, the proposed tabu search optimizes the total weighted tardiness for partial schedules in which some machines are currently assumed to have infinite capacity. In the context of tabu search, the shifting bottleneck heuristic features a long-term memory which helps to diversify the local search. We exploit this synergy to develop a state-of-the-art algorithm for the job shop total weighted tardiness problem (JS-TWT). The computational effectiveness of the algorithm is demonstrated on standard benchmark instances from the literature.     

Scheduling jobs with ready times and precedence constraints on parallel batch machines using metaheuristics

In this paper, we discuss a scheduling problem for parallel batch machines where the jobs have ready times. Problems of this type can be found in semiconductor wafer fabrication facilities (wafer fabs). In addition, we consider precedence constraints among the jobs. Such constraints arise, for example, in scheduling subproblems of the shifting bottleneck heuristic when complex job shop scheduling problems are tackled. We use the total weighted tardiness as the performance measure to be optimized. Hence, the problem is NP-hard and we have to rely on heuristic solution approaches. We consider a variable neighborhood search (VNS) scheme and a greedy randomized adaptive search procedure (GRASP) to compute efficient solutions. We assess the performance of the two metaheuristics based on a large set of randomly generated problem instances and based on instances from the literature. The obtained computational results demonstrate that VNS is a very fast heuristic that quickly leads to high-quality solutions, whereas the GRASP is slightly outperformed by the VNS approach. However, the GRASP approach has the advantage that it can be parallelized in a more natural manner compared to VNS.     

面向航空发动机的知识化制造系统拖期调度与自重构

针对某航空发动机装配线装配效率低、工人分配不合理等问题,建立面向航空发动机的知识化制造系统拖期调度和班组自重构优化模型.提出一种启发式算法,实现生产调度与班组配置的协同优化.在算法调度层中,针对航空发动机装配过程存在复杂约束这一特点,证明与产品拖期优化目标相关的工序排序性质,设计相应工序调整算法,给出工序在并行装配组上的初始分配方案和优化方案.在重构层,根据系统负载平衡的原则优化各装配班中装配组的数量.仿真实验结果表明了模型和所提出算法的有效性.     

Decomposition methods for large job shops

A rolling horizon heuristic is presented for large job shops, in which the total weighted tardiness must be minimized. The method divides a given instance into a number of subproblems, each having to correspond to a time window of the overall schedule, which are solved using a shifting bottleneck heuristic. A number of rules for defining each time window are derived. The method is tested by using instances up to 10 machines and 100 operations per machine, outperforming a shifting bottleneck heuristic that has been shown to generate close to optimal results.Scope and purposeThere has been a significant amount of research focused on the scheduling of a job shop, either minimizing the makespan or the tardiness. Although the results for small-size problems are satisfactory, there has been no approach as for yet middle- and large-size problems. This paper presents a heuristic that decomposes the problems on a time window basis, solving each subproblem using a shifting bottleneck heuristic. Its results for a due-date-related objective function are promising.     

A decomposition based hybrid heuristic algorithm for the joint passenger and freight train scheduling problem

We study the joint problem of scheduling passenger and freight trains for complex railway networks, where the objective is to minimize the tardiness of passenger trains at station stops and the delay of freight trains. We model the problem as a mixed integer program and propose a two-step decomposition heuristic to solve the problem. The heuristic first vertically decomposes the train schedules into a passenger train scheduling phase and then a freight train scheduling phase. In the freight train scheduling phase, we use a train-based decomposition to iteratively schedule each freight train. Experimental results show the efficiency and quality of the proposed heuristic algorithm on real world size problems.     

A heuristic for job shop scheduling to minimize total weighted tardiness

This paper considers the job shop scheduling problem to minimize the total weighted tardiness with job-specific due dates and delay penalties, and a heuristic algorithm based on the tree search procedure is developed for solving the problem. A certain job shop scheduling to minimize the maximum tardiness subject to fixed sub-schedules is solved at each node of the search tree, and the successor nodes are generated, where the sub-schedules of the operations are fixed. Thus, a schedule is obtained at each node, and the sub-optimum solution is determined among the obtained schedules. Computational results on some 10 jobs and 10 machines problems and 15 jobs and 15 machines problems show that the proposed algorithm can find the sub-optimum solutions with a little computation time.     

Scheduling independent jobs on uniform parallel machines to minimize tardiness criteria

The problem of scheduling N jobs on M uniform parallel machines is studied. The objective is to minimize the mean tardiness or the weighted sum of tardiness with weights based on jobs, on periods or both. For the mean tardiness criteria in the preemptive case, this problem is NP-hard but good solutions can be calculated with a transportation problem algorithm. In the nonpreemptive case the problem is therefore NP-hard, except for the cases with equal job processing times or with job due dates equal to job processing times. No dominant heuristic is known in the general nonpreemptive case. The author has developed a heuristic to solve the nonpreemptive scheduling problem with unrelated job processing times. Initially, the algorithm calculates a basic solution. Next, it considers the interchanges of job subsets to equal processing time sum interchanging resources (i.e. a machine for a given period). This paper models the scheduling problem. It presents the heuristic and its result quality, solving 576 problems for 18 problem sizes. An application of school timetable scheduling illustrates the use of this heuristic.     

A distributed shifting bottleneck heuristic for complex job shops

In this paper, we consider distributed versions of a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant process flows. Semiconductor wafer fabrication facilities are typical examples for manufacturing systems with these characteristics. The used performance measure is total weighted tardiness (TWT). We suggest a two-layer hierarchical approach in order to decompose the overall scheduling problem. The upper (or top) layer works on an aggregated model. Based on appropriately aggregated routes it determines start dates and planned due dates for the jobs within each single work area, where a work area is defined as a set of parallel machine groups. The lower (or base) layer uses the start dates and planned due dates in order to apply shifting bottleneck heuristic type solution approaches for the jobs in each single work area. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the heuristic. It turns out that the suggested approach outperforms a pure First In First Out (FIFO) dispatching scheme and provides a similar solution quality as the original modified shifting bottleneck heuristic.     

作业车间调度转换瓶颈算法的不可行解问题

文章讨论了作业车间调度问题转换瓶颈算法的一个缺陷。转换瓶颈算法是解决作业车间调度最小makespan(完工时间)问题的很有效的启发式算法。它是基于反复的解决某些单机调度问题。然而在转换瓶颈算法中用Carlier算法解单机调度问题并不总能得到可行解,文中给出了一个反例证明了有产生不可行解的情况。另外,文章还以简洁的方法证明了转换瓶颈算法若用Schrage算法替代Carlier算法解单机调度问题不会产生不可行解。     

Trade-off solutions in a single-machine scheduling problem for minimizing total earliness and maximum tardiness

This paper considers a single-machine scheduling problem involving minimization of the total earliness and the maximum tardiness. Four dominant properties for the precedence relationship between jobs in a search for an optimal solution are proposed. The lower bounds of the total earliness and the maximum tardiness of a subproblem are derived. The dominance properties and the lower bounds are implemented in the branchand-bound algorithm to facilitate the search for an optimal schedule. A heuristic algorithm is then developed to overcome the inefficiency of the branch-and-bound algorithm. Computational performance of the two algorithms is also investigated.     

A hybrid scheduling approach for a two-stage flexible flow shop with batch processing machines

In this paper, we discuss a flexible flow shop scheduling problem with batch processing machines at each stage and with jobs that have unequal ready times. Scheduling problems of this type can be found in semiconductor wafer fabrication facilities (wafer fabs). We are interested in minimizing the total weighted tardiness of the jobs. We present a mixed integer programming formulation. The batch scheduling problem is NP-hard. Therefore, an iterative stage-based decomposition approach is proposed that is hybridized with neighborhood search techniques. The decomposition scheme provides internal due dates and ready times for the jobs on the first and second stage, respectively. Each of the resulting parallel machine batch scheduling problems is solved by variable neighborhood search in each iteration. Based on the schedules of the subproblems, the internal due dates and ready times are updated. We present the results of designed computational experiments that also consider the number of machines assigned to each stage as a design factor. It turns out that the proposed hybrid approach outperforms an iterative decomposition scheme where a fairly simple heuristic based on time window decomposition and the apparent tardiness cost dispatching rule is used to solve the subproblems. Recommendations for the design of the two stages with respect to the number of parallel machines on each stage are given.     

A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine

This paper deals with the single machine scheduling problem to minimize the total weighted tardiness in the presence of sequence dependent setup. Firstly, a mathematical model is given to describe the problem formally. Since the problem is NP-hard, a general variable neighborhood search (GVNS) heuristic is proposed to solve it. Initial solution for the GVNS algorithm is obtained by using a constructive heuristic that is widely used in the literature for the problem. The proposed algorithm is tested on 120 benchmark instances. The results show that 37 out of 120 best known solutions in the literature are improved while 64 instances are solved equally. Next, the GVNS algorithm is applied to single machine scheduling problem with sequence dependent setup times to minimize the total tardiness problem without changing any implementation issues and the parameters of the GVNS algorithm. For this problem, 64 test instances are solved varying from small to large sizes. Among these 64 instances, 35 instances are solved to the optimality, 16 instances' best-known results are improved, and 6 instances are solved equally compared to the best-known results. Hence, it can be concluded that the GVNS algorithm is an effective, efficient and a robust algorithm for minimizing tardiness on a single machine in the presence of setup times.     

解并行多机提前/拖后调度问题的并行遗传算法

为有效地解决带有公共交货期的非等同并行多机提前/拖后调度问题,设计了一种分段扩展排列编码的混合遗传算法,使遗传编码能同时反映调度方案和公共交货期,并对其初始种群产生、交叉和变异方法也进行了研究。同时为了更好地适应调度实时性和解大规模此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,此算法是有效的,优于启发式算法和遗传算法,有着较高的并行性,并能适用于大规模非等同并行多机提前/拖后调度问题。     

Minimizing Total Tardiness: A Case Study in an Autoparts Factory

The application of heuristic procedures for solving a real scheduling problem that arises in an autoparts factory is reported in this paper. Due to the characteristics of the environment, the measure of performance considered is the minimization of the total tardiness of the jobs. The original problem is reduced to the single machine scheduling problem, and the dispatching rules EDD (earliest due date), SPT (shortest processing time), and the PSK algorithm are used to obtain approximate solutions. Computational tests and a comparison with the usual schedule are presented.     

Common due date assignment and scheduling with ready times

We consider the problem of scheduling a set of nonsimultaneously available jobs on one machine. Each job has a ready time only at or after which the job can be processed. All the jobs have a common due date, which needs to be determined. The problem is to determine a due date and a schedule so as to minimize a total penalty depending on the earliness, tardiness and due date. We show that this problem is strongly NP-hard and give an efficient algorithm that finds an optimal due date and schedule when either the job sequence is predetermined or all jobs have the same processing time. We also propose three approximation algorithms for the general and special cases together with their experimental analysis.

Scope and purpose

We consider the single machine due date assignment problem for scheduling jobs which are ready for processing at different times. The problem under consideration arises in production planning and scheduling concerning the setting of appropriate due dates for a number of customer orders arriving over time. Most of the earlier publications on this subject assumed that the jobs are ready for processing simultaneously. This assumption is too restrictive for real-life production systems where jobs arrive at different times. We show that the problem with unequal ready times is NP-hard and develop fast heuristic algorithms for it, and exact algorithms for two special cases.     

Single CNC machine scheduling with controllable processing times to minimize total weighted tardiness

Advanced manufacturing technologies, such as CNC machines, require significant investments, but also offer new capabilities to the manufacturers. One of the important capabilities of a CNC machine is the controllable processing times. By using this capability, the due date requirements of customers can be satisfied much more effectively. Processing times of the jobs on a CNC machine can be easily controlled via machining conditions such that they can be increased or decreased at the expense of tooling cost. Since scheduling decisions are very sensitive to the processing times, we solve the process planning and scheduling problems simultaneously. In this study, we consider the problem of scheduling a set of jobs on a single CNC machine to minimize the sum of total weighted tardiness, tooling and machining costs. We formulated the joint problem, which is NP-hard since the total weighted tardiness problem (with fixed processing times) is strongly NP-hard alone, as a nonlinear mixed integer program. We proposed a DP-based heuristic to solve the problem for a given sequence and designed a local search algorithm that uses it as a base heuristic.     

Local and global dominance conditions for the weighted earliness scheduling problem with no idle time

In this paper, we present dominance conditions for the single machine weighted earliness scheduling problem with no idle time. We also propose an algorithm that can be used to improve upper bounds for the weighted earliness criterion and lower bounds for an earliness/tardiness problem. The computational tests show that the algorithm is superior to an initial heuristic schedule and an existing adjacency condition.     

Local and global dominance conditions for the weighted earliness scheduling problem with no idle time

In this paper, we present dominance conditions for the single machine weighted earliness scheduling problem with no idle time. We also propose an algorithm that can be used to improve upper bounds for the weighted earliness criterion and lower bounds for an earliness/tardiness problem. The computational tests show that the algorithm is superior to an initial heuristic schedule and an existing adjacency condition.     

Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems

Earliness/tardiness scheduling problems with undetermined common due date which have wide application background in textile industry, mechanical industry, electronic industry and so on, are very important in the research fields such as industry engineering and CIMS. In this paper, a kind of genetic algorithm based on sectional code for minimizing the total cost of assignment of due date, earliness and tardiness in this kind of scheduling problem is proposed to determine the optimal common due date and the optimal scheduling policy for determining the job number and their processing order on each machine. Also, simulated annealing mechanism and the iterative heuristic fine-tuning operator are introduced into the genetic algorithm so as to construct three kinds of hybrid genetic algorithms with good performance. Numerical computational results focusing on the identical parallel machine scheduling problem and the general parallel machine scheduling problem shows that these algorithms outperform heuristic procedures, and fit for larger scale parallel machine earliness/tardiness scheduling problem. Moreover, with practical application data from one of the largest cotton colored weaving enterprises in China, numerical computational results show that these genetic algorithms are effective and robust, and that especially the performance of the hybrid genetic algorithm based on simulated annealing and the iterative heuristic fine-tuning operator is the best among them.     

瓶颈指向的启发式算法求解混合流水车间调度问题

针对以最小化时间表长为目标的复杂混合流水车间调度问题,提出了一种将机器布局和工件加工时间特征紧密结合的启发式算法.首先,充分利用各阶段平均机器负荷一般不相等的特点确定瓶颈阶段,构建初始工件排序.其次,针对在瓶颈阶段前加工时间较短而瓶颈阶段后加工时间相对较长的工件,在第1阶段优先开始加工.同时,在瓶颈阶段前的每一个阶段,每当有工件等待加工或同时完工时,优先选择瓶颈阶段前剩余加工时间最短的工件加工;在瓶颈阶段以及瓶颈阶段之后,则优先选择这台机器后剩余加工时间最长的工件加工.最后,采用工件交换和插入操作改进初始调度.用Carlier和Neron的Benchmark算例测试提出的启发式算法.将计算结果与NEH启发式算法进行了比较,平均偏差降低了0.0555%,表明这个启发式算法是有效的.