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.     

Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria

In textile industries, production facilities are established as multi-stage production flow shop facilities, where a production stage may be made up of parallel machines. This known as a flexible or hybrid flow shop environment. This paper considers the problem of scheduling n independent jobs in such an environment. In addition, we also consider the general case in which parallel machines at each stage may be unrelated. Each job is processed in ordered operations on a machine at each stage. Its release date and due date are given. The preemption of jobs is not permitted. We consider both sequence- and machine-dependent setup times. The problem is to determine a schedule that minimizes a convex combination of makespan and the number of tardy jobs. A 0–1 mixed integer program of the problem is formulated. Since this problem is NP-hard in the strong sense, we develop heuristic algorithms to solve it approximately. Firstly, several basic dispatching rules and well-known constructive heuristics for flow shop makespan scheduling problems are generalized to the problem under consideration. We sketch how, from a job sequence, a complete schedule for the flexible flow shop problem with unrelated parallel machines can be constructed. To improve the solutions, polynomial heuristic improvement methods based on shift moves of jobs are applied. Then, genetic algorithms are suggested. We discuss the components of these algorithms and test their parameters. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages.     

Flow shop scheduling with two batch processing machines and nonidentical job sizes

A batch processing machine can process several jobs simultaneously. In this research, we consider the problem of a two-stage flow shop with two batch processing machines to minimize the makespan. We assume that the processing time of a batch is the longest processing time among all the jobs in that batch and the sizes of the jobs are nonidentical. There is a limitation on batch sizes and the sum of job sizes in a batch must be less than or equal to the machine capacity. Since this problem is strongly nondeterministic polynomial time hard, we propose two heuristic algorithms. The first one is knowledge-based and the other is based on the batch first fit heuristic proposed previously. To further enhance the solution quality, two different simulated annealing (SA) algorithms based on the two constructive heuristics is also developed. Since heuristic methods for this problem has not been proposed previously, a lower bound is developed for evaluating the performance of the proposed methods. Several test problems have been solved by SAs and lower bound method and the results are compared. Computational studies show that both algorithms provide good results but the first SA (ARSA) algorithm considerably outperforms the second one (FLSA). In addition, the results of ARSA algorithm, optimal solutions, and lower bounds are compared for several small problems. The comparisons show that except for one instance, the ARSA could find the optimal solutions and the proposed lower bound provides small gaps comparing with the optimal solutions.     

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.     

A genetic algorithm and particle swarm optimization for no-wait flow shop problem with separable setup times and makespan criterion

This paper considers the problem of no-wait flow shop scheduling, in which a number of jobs are available for processing on a number of machines in a flow shop context with the added constraint that there should be no waiting time between consecutive operations of a job. Each operation has a separable setup time, meaning that the setup time of an operation is independent on the previous operations; and the machine can be prepared for a specific operation and remain idle before the operation actually starts. The considered objective function in this paper is the makespan. The problem is proven to be NP-hard. In this paper, two frameworks based on genetic algorithm and particle swarm optimization are developed to deal with the problem. For the case of no-wait flow shop problem without setup times, the developed algorithms are applied to a large number of benchmark problems from the literature. Computational results confirm that the proposed algorithms outperform other methods by improving many of the best-known solutions for the test problems. For the problems with setup time, the algorithms are compared against the famous 2-Opt algorithm. Such comparison reveals the efficiency of the proposed method in solving the problem when separable setup times are considered.     

Minimizing makespan in a two-machine no-wait flow shop with batch processing machines

Given a set of jobs and two batch processing machines (BPMs) arranged in a flow shop environment, the objective is to batch the jobs and sequence the batches such that the makespan is minimized. The job sizes, ready times, and processing times on the two BPMs are known. The batch processing machines can process a batch of jobs as long as the total size of all the jobs assigned to a batch does not exceed its capacity. Once the jobs are batched, the processing time of the batch on the first machine is equal to the longest processing job in the batch; processing time of the batch on the second machine is equal to the sum of processing times of all the jobs in the batch. The batches cannot wait between two machines (i.e., no-wait). The problem under study is NP-hard. We propose a mathematical formulation and present a particle swarm optimization (PSO) algorithm. The solution quality and run time of PSO is compared with a commercial solver used to solve the mathematical formulation. Experimental study clearly highlights the advantages, in terms of solution quality and run time, of using PSO to solve large-scale problems.     

Genetic algorithms for minimizing makespan in a flow shop with two capacitated batch processing machines

This paper considers a flow shop with two batch processing machines. The processing times of the job and their sizes are given. The batch processing machines can process multiple jobs simultaneously in a batch as long as the total size of all the jobs in a batch does not exceed its capacity. When the jobs are grouped into batches, the processing time of the batch is defined by the longest processing job in the batch. Batch processing machines are expensive and a bottleneck. Consequently, the objective is to minimize the makespan (or maximize the machine utilization). The scheduling problem under study is NP-hard, hence, a genetic algorithm (GA) is proposed. The effectiveness (in terms of solution quality and run time) of the GA approach is compared with a simulated annealing approach, a heuristic, and a commercial solver which was used to solve a mixed-integer formulation of the problem. Experimental study indicates that the GA approach outperforms the other approaches by reporting better solution.     

Two-machine, no-wait job shop problem with separable setup times and single-server constraints

No-wait job shop scheduling problems refer to the set of problems in which a number of jobs are available for processing on a number of machines in a job shop context with the added constraint that there should be no waiting time between consecutive operations of the jobs. In this paper, a two-machine, no-wait job shop problem with separable setup times and a single-server constraint is considered. The considered performance measure is the makespan. This problem is strongly NP-hard. A mathematical model of the problem is developed and a number of propositions are proven for the special cases. Moreover, a genetic algorithm is proposed in this paper to find the optimal (or near-optimal) solutions. In order to evaluate the developed algorithm, a number of small instances are solved to optimality using the developed mathematical model. The proposed algorithm is able to find the optimal solution of all of these cases. For larger instances, the developed algorithm has been compared with the 2-opt algorithm as well as a proposed lower bound. Computational results show the efficiency of the proposed algorithm in generating good quality solutions compared to the developed lower bounds and 2-opt algorithm.     

Bottleneck identification procedures for the job shop scheduling problem with applications to genetic algorithms

Two bottleneck identification algorithms (one for bottleneck machines and the other for bottleneck jobs) are presented for the job shop scheduling problem in which the total weighted tardiness must be minimized. The scheduling policies on bottleneck machines can have significant impact on the final scheduling performance, and therefore, they need to be optimized with more computational effort. Meanwhile, bottleneck jobs that can cause considerable deterioration to the solution quality also need to be considered with higher priority. In order to describe the characteristic information concerning such bottleneck machines and bottleneck jobs, a statistical approach is devised to obtain the bottleneck characteristic values for each machine, and, in addition, a fuzzy inference system is employed to transform human knowledge into the bottleneck characteristic values for each job. These bottleneck characteristic values reflect the features of both the objective function and the current optimization stage. Finally, the effectiveness of the two procedures is verified by specifically designed genetic algorithms.     

Scheduling on identical parallel machines to minimize total completion time with deadline and machine eligibility constraints

This study addresses the identical parallel machine scheduling problem with job deadlines and machine eligibility constraints to minimize total job completion time. Jobs must be completed before or at a deadline and preemptions are not allowed. Every job is allowed to be processed on a specified subset of machines. This problem is NP-hard. A heuristic and a branch and bound algorithm are developed to solve the problem. For the branch and bound algorithm, a lower bound based on the dual solution of the assignment problem is proposed and the heuristic serves as the initial upper bound. Many dominance rules are developed to curtail the branching nodes during the search procedure. Computational results indicate that the lower bound improves the performance of those in the literature in terms of execution time, and heuristic consistently generates a good quality schedule.     

Generating non-permutation schedules in flowline-based manufacturing sytems with sequence-dependent setup times of jobs: a heuristic approach

A flowline-based manufacturing system is a manufacturing environment where machines are arranged in accordance with the order of processing of jobs, with all jobs having an identical and unidirectional flow pattern through the machines; however, some or all jobs may have missing operations on some machines. In several practical situations the setup times of jobs are separable, significant and sequence-dependent. The problem of scheduling in such a flowline-based manufacturing system is considered with the focus on the development of non-permutation schedules. The deficiency of using the existing set of recursive equations in developing the timetable for permutation schedules is first highlighted, and a correct and modified set of recursive equations to take account of the missing operations properly is formulated. A simple heuristic procedure to derive non-permutation schedules from a given permutation sequence is proposed subsequently. Through extensive computational experimentation, it is shown that the proposed heuristic procedure yields solutions of good quality.     

A novel hybrid genetic algorithm for the open shop scheduling problem

In this paper, a hybrid genetic algorithm is proposed for the open shop scheduling problem with the objective of minimizing the makespan. In the proposed algorithm, a specialized crossover operator is used that preserves the relative order of jobs on machines and a strategy is applied to prevent from searching redundant solutions in the mutation operator. Moreover, an iterative optimization heuristic is employed which uses the concept of randomized active schedules, a dispatching index based on the longest remaining processing time rule and a lower bound to further decrease the search space. Computational results show that the proposed algorithm outperforms other genetic algorithms and is very competitive with well-known metaheuristics available in the literature.     

Optimal parallel machines scheduling with machine availability and eligibility constraints

In reality, the machine might become unavailable due to machine breakdowns or various inevitable reasons, and machine might have different capability to processing job. Motivated by this, we consider the problem of scheduling n non-preemptive and independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the maximum lateness. Each machine is capable of processing at specific availability intervals. We develop a branch and bound algorithm applying several immediate selection rules for solving this scheduling problem.     

Due-date scheduling on parallel machines with job splitting and sequence-dependent major/minor setup times

This paper addresses job scheduling problems with parallel machines. To satisfy customers better in a manufacturing company, meeting due dates has been an important performance metric. Besides the numerous other factors affecting due date satisfaction, the splitting of a job through parallel machines can contribute to the reduction of production lead time, resulting in less job tardiness against their due dates. Thus, this paper presents heuristic algorithms for minimizing total tardiness of jobs to meet their due dates in a manufacturing shop with identically functioning machines. The algorithms take into account job splitting and sequence-dependent major/minor setup times. The performance of the proposed heuristics is compared with that of past three algorithms in the literature.     

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

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

A joint GA+DP approach for single burn-in oven scheduling problems with makespan criterion

This research is motivated by the scheduling problem found in the burn-in operation of semiconductor final testing, where jobs are associated with release times, processing times, and sizes. The burn-in ovens are modeled as batch-processing machines which can process a batch of several jobs as long as the total sizes of the jobs do not exceed the machine capacity, and the processing time of a batch is equal to the longest time among all the jobs in the batch. Moreover, this paper attempts to schedule jobs on a single batch-processing machine to minimize makespan. A joint GA+DP algorithm is proposed involving two stages: (1) the formation of job sequence by genetic algorithm operators, and (2) the formation of batches by a dynamic programming algorithm. Computational experiments are given to examine the performance of the proposed algorithm. The experimental results indicate that the joint GA+DP approach has well improved on all instances with respect to solution quality and runtime.     

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.     

A two-criteria objective function flexible flowshop scheduling problem with machine eligibility constraint

This research deals with a flexible flowshop scheduling problem with the arrival and delivery of jobs in groups and processing them individually. Each group of jobs has a specific release time. Due to the special characteristics of each job, only a specific group of machines in each stage are eligible to process that job. All jobs in a group should be delivered at the same time after processing. The objectives of the problem are the minimization of the sum of the completion time of groups on one hand and the minimization of sum of the differences between the completion time of jobs and the delivery time of the group containing that job (waiting period) on the other hand. The problem can be stated as FF_c /r _j , M _j /irreg based on existing scheduling notations. This problem has many applications in the production and service industries such as ceramic tile manufacturing companies and restaurants. A mathematical model has been proposed to solve the problem. Since the research problem is shown to be NP-complete, a particle swarm optimization (PSO) algorithm is applied to solve the problem approximately. Based on the frequency of using local search procedure, four scenarios of PSO have been developed. The algorithms are compared by applying experimental design techniques on random test problems with different sizes. The results show that the PSO algorithm enhanced with local search for all particles has a weaker performance than the other scenarios in solving large-sized problems.     

Combined column generation and constructive heuristic for a proportionate flexible flow shop scheduling

In a proportionate flow shop problem, jobs have to be processed through a fixed sequence of machines, and processing time for each job is equal on all machines. Such a problem has seldom been tackled. Proportionate flexible flow shop (PFFS) scheduling problems combine the properties of proportionate flow shop scheduling problems and parallel machine scheduling problems. This study presents a combined approach based on column generation (CG) for a PFFS problem with the criterion to minimize the objective of the total weighted completion time (TWCT). Minimizing TWCT in a PFFS problem significantly differs from the parallel-identical-machine scheduling problem, an optimal schedule in which jobs on each machine are in the weighted shortest processing time (WSPT) order. This combined approach adopts a CG approach to effectively handle job assignments to machines, and a constructive heuristic to obtain an optimal sequence for a single machine. Experimental results show the effectiveness of the combined approach in obtaining excellent quality solutions in a reasonable time, especially for large-scale problems.     

Two-agent group scheduling with deteriorating jobs on a single machine

This paper considers the two-agent scheduling problems with deteriorating jobs and group technology on a single machine, where the objective is to minimize the total completion time of the first agent with the restriction that the maximum cost of the second agent cannot exceed a given upper bound. Two agents compete to perform their respective jobs on a common single machine, and each agent has his own criterion to optimize. We introduce deteriorating jobs and group technology into the two-agent single-machine scheduling where the job processing times and group setup times are both functions of their starting times. There are two different linear deterioration functions. We propose the optimal properties and present the optimal polynomial time algorithms for two different scheduling problems, respectively.