Ant colony optimization for unrelated parallel machine scheduling

Meeting due dates is a major issue in most manufacturing systems, and one effective measure for due dates is total weighted tardiness. In this research, we consider an ant colony optimization (ACO) algorithm incorporating a number of new ideas (heuristic initial solution, machine reselection step, and local search procedure) to solve the problem of scheduling unrelated parallel machines to minimize total weighted tardiness. The problem is NP-hard in the strong sense, because the single machine case is already NP-hard in the strong sense. Computational results show that the proposed ACO algorithm outperforms other existing algorithms in terms of total weighted tardiness.     

A due date density-based categorising heuristic for parallel machines scheduling

The effective management of shop floor resources is an important factor in achieving the goals of a manufacturing company. The need for effective scheduling is particularly strong in complex manufacturing environments. This paper presents an efficient due date density-based categorising heuristic to minimise the total weighted tardiness (TWT) of a set of tasks with known processing times, due dates, weights and sequence-dependent setup times for parallel machines scheduling. The proposed heuristic is composed of four phases. In the first phase, jobs are listed by the earliest due date (EDD). The second phase computes the due date gaps between listed jobs and categorises the jobs based on the due date density. In the third phase, the sequence of jobs is improved by a tabu search (TS) method. The fourth phase allocates each job to machines. The comprehensive simulation results show that the proposed heuristic performs better than other existing heuristics at a significantly reduced total weighted tardiness.     

并行多机提前/拖期调度的启发式算法

准时制生产模式要求生产任务必须在交货期内完成.实际生产中这一问题受很多约束的影响变得非常复杂.文章针对任务动态到达、任务转换存在的调整时间和交货期、提前/拖期单位成本各不相同的并行多机上任务排序问题进行了分析,设计了一种解决并行多机提前/拖期调度的启发式近似求解算法.大量实验数据和应用实例充分表明文章所提的启发式算法是有效的.     

Due windows group scheduling using an effective hybrid optimization approach

This paper considers the problem of scheduling part families (groups) and jobs within each part family in a hybrid flow shop manufacturing cell with sequence-dependent family setups times where jobs should be completed at times as close as possible to their respective due dates, and hence both earliness and tardiness should be penalized while processing parts (jobs) in each family together. It is assumed that earliness and tardiness penalties will not occur if a job is completed within the due window. The objective is to determine a schedule that minimizes sum of the earliness and tardiness of jobs. To this problem, the hybrid metaheuristic algorithm combined elements from particle swarm optimization; simulated annealing and variable neighborhood search are developed. The aim of using a hybrid metaheuristic is to raise the level of generality so as to be able to apply the same solution method to several problems. Problem sizes ranging in size from small, medium, to large are considered along with three levels of flexibility. The higher the number of stages and the number of parallel machines in each stage, the higher is the flexibility introduced into the problem. A design of experiments approach is employed to calibrate the parameters and operators of the algorithm. We present computational experiments on 126 problems and compare the results with the simulated annealing and genetic algorithms that presented recently. The computational results show that our proposed algorithm is more efficient than the other methods.     

Minimizing total weighted tardiness on heterogeneous batch processors with incompatible job families

In this paper, we address a scheduling problem for minimizing total weighted tardiness. The background for the paper is derived from the automobile gear manufacturing process. We consider the bottleneck operation of heat treatment stage of gear manufacturing. Real-life scenarios like unequal release times, incompatible job families, non-identical job sizes, heterogeneous batch processors, and allowance for job splitting have been considered. We have developed a mathematical model which takes into account dynamic starting conditions. The problem considered in this study is NP-hard in nature, and hence heuristic algorithms have been proposed to address it. For real-life large-size problems, the performance of the proposed heuristic algorithms is evaluated using the method of estimated optimal solution available in literature. Extensive computational analyses reveal that the proposed heuristic algorithms are capable of consistently obtaining near-optimal statistically estimated solutions in very reasonable computational time.     

Parallel machine scheduling with earliness-tardiness penalties and space limits

In order to maximize an availability of machine and utilization of space, the parallel machines scheduling problem with space limit is frequently discussed in the industrial field. In this paper, we consider the parallel machine scheduling problem in which n jobs having different release times, due dates, and space limits are to be scheduled on m parallel machines. The objective function is to minimize the weighted sum of earliness and tardiness. To solve this problem, a heuristic is developed which is divided into three modules hierarchically: job selection, machine selection and job sequencing, and solution improvement. To illustrate its effectiveness, a proposed heuristic is compared with genetic algorithm (GA), hybrid genetic algorithm (HGA), and tabu search (TS), which are well-known meta-heuristics in a large number of randomly generated test problems based on the field situation. Also, we determine the job selection rule that is suitable to the problem situation considered in this paper and show the effectiveness of our heuristic method.     

Job shop scheduling based on earliness and tardiness penalties with due dates and deadlines: an enhanced genetic algorithm

This paper studies a job shop scheduling problem with due dates and deadlines in the presence of tardiness and earliness penalties. Due dates are desired completion dates of jobs given by the customer, while deadlines are determined by the manufacturer based on customer due dates. Due dates can be violated at the cost of tardiness, whereas deadlines must be met and cannot be violated. The aforementioned scheduling problem, which is NP-hard, can be formulated with the objective function of minimizing the sum of weighted earliness and weighted tardiness of jobs subject to due dates and deadlines. In order to solve this problem, an enhanced genetic algorithm (EGA) is introduced in this paper. EGA utilizes an operation-based scheme to represent schedules as chromosomes. After the initial population of chromosomes is randomly generated, each chromosome is processed through a three-stage decoder, which first reduces tardiness based on due dates, second ensures deadlines are not violated, and finally reduces earliness based on due dates. After the population size is reached, EGA continues with selection, crossover, and mutation. The proposed algorithm is tested on 180 job shop scheduling problems of varying sizes and its performance is discussed.     

Scheduling Jobs on Parallel Machines with Sequence-Dependent Family Set-up Times

This paper proposes an efficient heuristic to minimise the total weighted tardiness of a set of tasks with known processing times, due dates, weights and family types for parallel machines. A three-phase heuristic is presented to minimise total weighted tardiness. In the first phase, jobs are listed by the earliest due date and then divided into small job-sets according to a decision parameter. In the second phase, jobs are grouped by the due date within applicable families using apparent tardiness cost with set-up (ATCS), and the sequence of jobs within families is improved through the use of the tabu search method. In the third phase, jobs are allocated to machines using a threshold value and a look-ahead parameter. The comprehensive simulation results show that the proposed heuristic performs better than the ATCS and rolling horizon procedure at a significantly reduced total weighted tardiness.     

Parallel work center scheduling with release dates, due dates, and resource-dependent processing times

This study addresses a job scheduling and resource allocation (JSRA) problem with distinct release dates and due dates to minimize total tardiness in parallel work centers in a multi-processor environment. To solve the problem, we propose a hybrid genetic algorithm with release- and due date-based decomposition heuristic (GARDDH). Five small-sized test problems are performed to evaluate the performance of the GARDDH, the conventional GA (CGA), and the optimum solution obtained using Lingo 7.0. Another three large-sized test problems are performed to evaluate the performance of the GARDDH and the CGA. Computational results show that the GARDDH performs well for large-sized problems.     

A new hybrid parallel algorithm for consistent-sized batch splitting job shop scheduling on alternative machines with forbidden intervals

Considering alternative machines for operations, forbidden intervals during which machines cannot be available and a job’s batch size greater than one in the real manufacturing environment, this paper studies the batch splitting scheduling problem on alternative machines with forbidden intervals, based on the objective to minimize the makespan. A scheduling model is established, taking before-arrival set-up, processing, and transfer time into account. And a new hybrid parallel algorithm, based on differential evolution and genetic algorithm, is brought forward to solve both the batch splitting problem and the batch scheduling problem by assuming a common number of sub-batches in advance. A solution consists of the actual optimum number of sub-batches for each job, the optimum batch size for each sub-batch, and the optimum sequence of operations for these sub-batches. Experiments on the performance of the proposed algorithm under different common numbers of sub-batches are carried out. The results of simulations indicate that the algorithm is feasible and efficient.     

Multiple common due dates assignment and scheduling problems with resource allocation and general position-dependent deterioration effect

This paper investigates the single-machine multiple common due dates assignment and scheduling problems in which the processing time of a job depends on its position in a job sequence and its resource allocation. We examine the general position-dependent deterioration effect and two models of resource allocation. The objective function is to minimize a total penalty function containing earliness, tardiness, due date, and resource consumption costs. We introduce two polynomial time algorithms to solve the considered problems. Since the two algorithms solve the problems in polynomial time, they can solve large-scale instances of the problem under study in little time.     

Scheduling jobs on parallel machines: a restricted tabu search approach

Many real scheduling problems are often much more complex than problems that are analytically tractable. The main difficulty in obtaining optimal job schedules arises from the existence of sequence dependent setup times among jobs and job release times. In this paper, we present a restricted tabu search algorithm that schedules jobs on parallel machines in order to minimise the maximum lateness of the jobs. The jobs have release times and due dates, and sequence-dependent setup times exist between the jobs. The parallel machines are either identical or non-identical in terms of the processing times of the jobs. The restricted tabu search algorithm employs a restricted search with the elimination of non-effective job moves, for finding the best neighbourhood schedule. The restricted search algorithm reduces search effort significantly while obtaining good quality final schedule. The experimental results show that the proposed algorithm obtains much better solutions more quickly than other heuristic algorithms such as the Rolling Horizon Procedure (RHP) heuristic, the basic tabu search and simulated annealing.     

Minimization of maximum tardiness on unrelated parallel machines with process restrictions and setups

We consider the problem of scheduling N jobs on M unrelated parallel machines to minimize maximum tardiness. Each job has a due date and requires a single stage of processing. A setup for dies is incurred if the type of the job scheduled is different from the previous one on that machine. For each die type, the number of dies is restricted. Because of the mechanical structure of the machines and the fitness of dies to each machine, the processing time depends on both the job and the machine. In this paper, an efficient heuristic based on guided search, record-to-record travel, and tabu lists is presented to minimize maximum tardiness. Computational characteristics of the proposed heuristic are evaluated through extensive experiments, which show that the proposed heuristic outperforms a simulated annealing method tested and is able to prescribe the optimal solutions for problems in small scales.     

Minimizing total weighted tardiness on heterogeneous batch processing machines with incompatible job families

This paper addresses a specific class of scheduling parallel batching problem, which is observed in steel casting industries. The focus of this research is to minimize the total weighted tardiness on heterogeneous batch processing machines under conditions of dynamic job arrivals, incompatible job families and non-identical job sizes. This type of parallel batching problem arises in a number of different settings, including diffusion in wafer fabrication, heat treatment operations in aircraft industries, and metal working. The problem is viewed as a three stage-decision-problem: the first stage involves selecting a machine from the heterogeneous batch processing machines for scheduling; the second stage involves the selection of a job family from the available incompatible job families; and the third stage involves the selection of a set of jobs to create a batch from the selected job family based on the capacity of the selected batch-processing machine. Since the problem is NP-hard, a few greedy heuristics are proposed. The computational experiments show that the proposed greedy heuristic algorithms are capable of consistently obtaining near-optimal solutions (statistically estimated) in very reasonable computational time on a Pentium III 650 Mz with 128 MB RAM.     

Minimizing total weighted tardiness on heterogeneous batch processing machines with incompatible job families

This paper addresses a specific class of scheduling parallel batching problem, which is observed in steel casting industries. The focus of this research is to minimize the total weighted tardiness on heterogeneous batch processing machines under conditions of dynamic job arrivals, incompatible job families and non-identical job sizes. This type of parallel batching problem arises in a number of different settings, including diffusion in wafer fabrication, heat treatment operations in aircraft industries, and metal working. The problem is viewed as a three stage-decision-problem: the first stage involves selecting a machine from the heterogeneous batch processing machines for scheduling; the second stage involves the selection of a job family from the available incompatible job families; and the third stage involves the selection of a set of jobs to create a batch from the selected job family based on the capacity of the selected batch-processing machine. Since the problem is NP-hard, a few greedy heuristics are proposed. The computational experiments show that the proposed greedy heuristic algorithms are capable of consistently obtaining near-optimal solutions (statistically estimated) in very reasonable computational time on a Pentium III 650 Mz with 128 MB RAM.     

A rolling horizon job shop rescheduling strategy in the dynamic environment

In this paper, the job shop scheduling problem in a dynamic environment is studied. Jobs arrive continuously, machines breakdown, machines are repaired and due dates of jobs may change during processing. Inspired by the rolling horizon optimisation method from predictive control technology, a periodic and event-driven rolling horizon scheduling strategy is presented and adapted to continuous processing in a changing environment. The scheduling algorithm is a hybrid of genetic algorithms and dispatching rules for solving the job shop scheduling problem with sequence-dependent set-up time and due date constraints. Simulation results show that the proposed strategy is more suitable for a dynamic job shop environment than the static scheduling strategy.     

Performance Comparison of Some Classes of Flexible Flow Shops and Job Shops

Flexible manufacturing systems (FMSs) for two-stage production may possess a variety of operating flexibilities in the form of tooling capabilities for the machines and alternative routings for each operation. In this paper, we compare the throughput performance of several flexible flow shop and job shop designs. We consider two-stage assembly flow shops with m parallel machines in stage 1 and a single assembly facility in stage 2. Every upstream operation can be processed by any one of the machines in stage 1 prior to the assembly stage. We also study a similar design where every stage 1 operation is processed by a predetermined machine. For both designs, we present heuristic algorithms with good worst-case error bounds and show that the average performance of these algorithms is near optimal. The algorithms presented are used to compare the performance of the two designs with each other and other related flexible flow shop designs. It is shown, both analytically and experimentally, that the mode of flexibility possessed by a design has implications on the throughput performance of the production system.     

Analysis of dispatching rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times

Stochastic dynamic job shop scheduling problem with consideration of sequence-dependent setup times are among the most difficult classes of scheduling problems. This paper assesses the performance of nine dispatching rules in such shop from makespan, mean flow time, maximum flow time, mean tardiness, maximum tardiness, number of tardy jobs, total setups and mean setup time performance measures viewpoint. A discrete event simulation model of a stochastic dynamic job shop manufacturing system is developed for investigation purpose. Nine dispatching rules identified from literature are incorporated in the simulation model. The simulation experiments are conducted under due date tightness factor of 3, shop utilization percentage of 90 % and setup times less than processing times. Results indicate that shortest setup time (SIMSET) rule provides the best performance for mean flow time and number of tardy jobs measures. The job with similar setup and modified earliest due date (JMEDD) rule provides the best performance for makespan, maximum flow time, mean tardiness, maximum tardiness, total setups and mean setup time measures.     

一类带有deadline约束的作业车间提前/拖期调度问题研究

针对带有零件deadline时间约束的一类作业车间提前/拖期调度问题,设计了一种改进型遗传算法(EGA)。EGA算法采用拖期优先的调度策略,将原有的非正规性能指标的E/T调度问题转化为拖期子问题、修复子问题和提前子问题,以此来降低E/T调度问题的求解复杂度。采用基于工序的编码方法,在染色体解码过程中,分别采用了主动解码、染色体修复和逆向重调度三阶段的解码操作,以期实现在满足零件deadline约束的前提下尽可能降低提前/拖期惩罚总成本。180个调度测试用例仿真结果表明,EGA算法在解决问题数、寻优能力、调度结果的均衡性等方面具有一定的优势。     

Minimization of maximum tardiness on unrelated parallel machines with process restrictions and setups

We consider the problem of schedulingN jobs onM unrelated parallel machines to minimize maximum tardiness. Each job has a due date and requires a single stage of processing. A setup for dies is incurred if the type of the job scheduled is different from the previous one on that machine. For each die type, the number of dies is restricted. Because of the mechanical structure of the machines and the fitness of dies to each machine, the processing time depends on both the job and the machine. In this paper, an efficient heuristic based on guided search, record-to-record travel, and tabu lists is presented to minimize maximum tardiness. Computational characteristics of the proposed heuristic are evaluated through extensive experiments, which show that the proposed heuristic outperforms a simulated annealing method tested and is able to prescribe the optimal solutions for problems in small scales.