Meta-heuristics to solve single-machine scheduling problem with sequence-dependent setup time and deteriorating jobs

This paper tackles the single-machine scheduling problem in which there are sequence-dependent setup times and deteriorating jobs. In this regard, a mathematical model has been formulated to minimize makespan (C _max). Afterwards, genetic and tabu search algorithms have been developed. Since the population diversity is a very important issue in preventing neighborhood search from trapping in a local optimum, some methods have been applied to genetic algorithm in order to maintain population diversity, and the final results show the effectiveness of these methods. The calibration of genetic algorithm parameters and operators is performed using design of experiments. Finally, several examples are produced to illustrate the proposed approach.     

A hybrid imperialist competitive algorithm for single-machine scheduling problem with linear earliness and quadratic tardiness penalties

In this paper, we study single-machine scheduling problem when each job is considered with linear earliness and quadratic tardiness penalties with no machine idle time. Here the objective is to find the best sequence of jobs in the reasonable time. This model was studied in several researches, and some algorithms were proposed to solve it such as genetic algorithm. As the size of problem increased, such algorithms were not effective and efficient. Hence, we proposed the hybrid imperialist competitive algorithm. The proposed algorithm is based upon the imperialist competitive algorithm and genetic algorithm concepts. This algorithm was tested in problems with different sizes. The results denoted that the hybrid algorithm can solve different size of problem in reasonable time. This procedure showed its efficiency in medium- and large-sized problems as compared with other available methods.     

Mathematical model and parallel genetic algorithm for hybrid flexible flowshop lot streaming problem

Lot streaming is the technique of splitting a given job into sublots to allow the overlapping of successive operations in multi-stage manufacturing systems thereby reducing production makespan. Several research articles appeared in literature to solve this problem and most of these studies are limited to pure flowshop environments where there is only a single machine in each stage. On the other hand, because of the applicability of hybrid flowshops in different manufacturing settings, the scheduling of these types of shops is also extensively studied by several authors. However, the issue of lot streaming in hybrid flowshop environment is not well studied. In this paper, we aim to contribute in bridging the gap between the research efforts in flowshop lot streaming and hybrid flowshop scheduling. We propose a mathematical model and a genetic algorithm for the lot streaming problem of several jobs in multi-stage flowshops where at each stage there are unrelated parallel machines. The jobs may skip some of the stages, and therefore, the considered system is a complex generalized flowshop. The proposed genetic algorithm is executed on both sequential and parallel computing platforms. Numerical examples showed that the parallel implementation greatly improved the computational performance of the developed heuristic.     

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.     

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.     

Improved genetic algorithm for the job-shop scheduling problem

In this paper, an improved genetic algorithm, called the hybrid Taguchi-genetic algorithm (HTGA), is proposed to solve the job-shop scheduling problem (JSP). The HTGA approach is a method of combining the traditional genetic algorithm (TGA), which has a powerful global exploration capability, with the Taguchi method, which can exploit the optimal offspring. The Taguchi method is inserted between crossover and mutation operations of a TGA. Then, the systematic reasoning ability of the Taguchi method is incorporated in the crossover operations to systematically select the better genes to achieve crossover, and consequently enhance the genetic algorithm. Therefore, the proposed HTGA approach possesses the merits of global exploration and robustness. The proposed HTGA approach is effectively applied to solve the famous Fisher-Thompson benchmarks of 10 jobs to 10 machines and 20 jobs to 5 machines for the JSP. In these studied problems, there are numerous local optima so that these studied problems are challenging enough for evaluating the performances of any proposed GA-based approaches. The computational experiments show that the proposed HTGA approach can obtain both better and more robust results than other GA-based methods reported recently.     

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.     

Scheduling in aerospace composite manufacturing systems: a two-stage hybrid flow shop problem

This research investigates a real-world complex two-stage hybrid flow shop scheduling problem which is faced during the manufacturing of composite aerospace components. There are a number of new constraints to be taken into account in this special hybrid flow shop, in particular limited physical capacity of the intermediate buffer, limited waiting time between processing stages, and limited tools/molds used in both stages in each production cycle. We propose a discrete-time mixed integer linear programming model with an underlying branch and bound algorithm, to solve small- and medium-size problems (up to 100 jobs). To solve the large instances of the problem (up to 300 jobs), a genetic algorithm with a novel crossover operator is developed. A new heuristic method is introduced to generate the initial population of the genetic algorithm. The results show the high level of computational efficiency and accuracy of the proposed genetic algorithm when compared to the optimal solutions obtained from the mathematical model. The results also show that the proposed genetic algorithm outperforms the conventional dispatching rules (i.e., shortest processing time, earliest dues date and longest processing time) when applied to large-size problems. A real case study undertaken at one of the leading aerospace companies in Canada is used to formulate the model, collect data for the parameters of the model, and analyze the results.     

Solving a new mathematical model for a hybrid flow shop scheduling problem with a processor assignment by a genetic algorithm

This paper presents a new mathematical model for a hybrid flow shop scheduling problem with a processor assignment that minimizes makespan (i.e., C _max) and cost of assigning a number of processors to stages. In this problem, it is assumed that there are a number of parallel identical processors which are assigned to all of the stages with an unlimited intermediate storage between any two successive stages. To solve such a hard problem, first a new heuristic algorithm is proposed to compute the makespan that is embedded in the proposed genetic algorithm in order to find the best sequence of jobs, and then processors are assigned to the stages simultaneously. A number of test problems have been solved and related results are illustrated and analyzed.     

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.     

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.     

A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem

This paper considers a single batch machine dynamic scheduling problem, which is readily found in the burn-in operation of semiconductor manufacturing. The batch machine can process several jobs as a batch simultaneously, within the capacity limit of the machine, and the processing time is represented by the longest processing time among all jobs in a batch. For a single batch machine problem with arbitrary job release time, we proposed an improved algorithm (merge-split procedure) to refine the solution obtained by the LPT-BFF heuristic, and two versions of a hybrid genetic algorithm (GA) are introduced in this paper. Each version of the hybrid GA diversifies job sequences using the GA operators in stage 1, forms batches in stage 2, and finally sequence the batches in stage 3. The difference is that merge-split procedures are involved in the second version of the hybrid GA. Computational experiments showed that the hybrid GA would obtain satisfactory average solution quality and the merge-split procedures would be good at reinforcing the solution consistency of the hybrid GA.     

Multi-objective flexible flow lines with due window, time lag, and job rejection

This paper presents a multi-objective flexible flow shop scheduling problem with limited time lag between stages. n jobs are available to schedule in a predetermined due window. A mixed integer linear programming model with the objectives of maximizing the total profit gained from scheduled jobs and minimizing deviation from the due date is introduced. Due to non-deterministic polynomial-time-hard complexity, the problem is solved with an efficient genetic algorithm. A heuristic mechanism is devised in every generation of the genetic algorithm to assure the solution feasibility. This heuristic also decreases the total solution time by reducing the search space. Computational results show that the presented approach finds solutions of good quality in reasonable runtimes.     

A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs

In this paper the problem of permutation flow shop scheduling with the objectives of minimizing the makespan and total flow time of jobs is considered. A Pareto-ranking based multi-objective genetic algorithm, called a Pareto genetic algorithm (GA) with an archive of non-dominated solutions subjected to a local search (PGA-ALS) is proposed. The proposed algorithm makes use of the principle of non-dominated sorting, coupled with the use of a metric for crowding distance being used as a secondary criterion. This approach is intended to alleviate the problem of genetic drift in GA methodology. In addition, the proposed genetic algorithm maintains an archive of non-dominated solutions that are being updated and improved through the implementation of local search techniques at the end of every generation. A relative evaluation of the proposed genetic algorithm and the existing best multi-objective algorithms for flow shop scheduling is carried by considering the benchmark flow shop scheduling problems. The non-dominated sets obtained from each of the existing algorithms and the proposed PGA-ALS algorithm are compared, and subsequently combined to obtain a net non-dominated front. It is found that most of the solutions in the net non-dominated front are yielded by the proposed PGA-ALS.     

Production planning in virtual cell of reconfiguration manufacturing system using genetic algorithm

This paper focuses on the scheduling problem of the reconfiguration manufacturing system (RMS) for execution level, where the final objective is to output a production plan. The practical situation in Chinese factory is analyzed, and the characteristics are summarized into the contradiction between flow and job shop production. In order to handle this problem, a new production planning algorithm in virtual cells is proposed for RMS using an improved genetic algorithm. The advantages of this algorithm have three parts: (1) the virtual cell reconfiguration is formed to assist making production plans through providing relationship among task families and machines from cell formation; (2) The operation buffer algorithm is developed for flow style production in cells, which can realize the nonstop processing for flow style jobs; and (3) The multicell sharing method is proposed to schedule job shop jobs in order to fully utilize manufacturing capability among machines in multicells. Based on the above advantages, an improved genetic algorithm is developed to output scheduling plan. At last, the algorithm is tested in different instances with LINGO and the other genetic algorithm, and then the scheduling solution comparison shows the proposed algorithm can get a better optimum result with the same time using the comparison algorithm.     

Minimizing the makespan and the system unavailability in parallel machine scheduling problem: a similarity-based genetic algorithm

This paper is devoted to ponder a joint production and maintenance problem. For solving the problem, a genetic algorithm named similarity-based subpopulation genetic algorithm (SBSPGA) is introduced. SBSPGA is presented based on a well-known evolutionary algorithm, the subpopulation genetic algorithm II (SPGA-II). Compared with the SPGA-II, the innovation of the SBSPGA could be divided into two parts: (1) using a similarity model for the elitism strategy and (2) performing the algorithm in just one stage. To tackle the maintenance aspect, reliability models are employed in this paper. The aim of this paper was to optimize two objectives: minimization of the makespan for the production part and minimization of the system unavailability for the maintenance part. To execute our proposed problem, two decisions must be made at the same time: achieving the best assignment of n jobs on m machines to minimize the makespan and determining the time at which the preventive maintenance activities must be performed to minimize the system unavailability. The maintenance activity numbers and the maintenance intervals are not fixed in advanced. Promising the acquired results, a benchmark with tremendous number of test instances (more than 5,000) is employed.     

Two meta-heuristics for solving a new two-machine flowshop scheduling problem with the learning effect and dynamic arrivals

This paper develops a new mathematical model and proposes two meta-heuristics for solving a two-machine flowshop scheduling problem that minimizes bi-objectives, namely the total idle time and the mean deviation from a common due data. In this paper, we assume the arrival time of jobs is dynamic, in which each job has a time window and can arrive in its time window randomly. We also assume the learning effect on the processing times considering as a position-dependent effect. Since the problem is an NP-hard one, we present a multiobjective genetic algorithm (MOGA) and a multiobjective simulated annealing (MOSA) algorithm to solve the given problems. The computational results confirm that the proposed MOGA has a better solution in comparison with the proposed MOSA, especially in large-sized problems.     

Minimizing the number of tardy jobs and maximum earliness in the single machine scheduling using an artificial immune system

Nowadays, the importance of timely delivery, which is based on the just in time concept, has caused a number of criteria related to scheduling problems to be taken into consideration. One of the most important of these criteria is maximum earliness to control final costs and number of tardy jobs in an attempt to win customer satisfaction. In this paper, the strongly NP-hard problem of the single machine scheduling with two criteria, i.e., maximum earliness and number of tardy jobs, has been considered. For this purpose, artificial immune system which is inspired by the immunology theory in biology has been used. This algorithm is applied to different instances of small to large sizes and the obtained results is compared with those obtained from a heuristic method and a genetic algorithm reported in the literature. Computational results show a significant preference for the algorithm proposed in this paper.     

A genetic algorithm for solving no-wait flexible flow lines with due window and job rejection

This paper addresses a no-wait multi-stage flexible flow shop problem. There are n jobs to complete in a predetermined due window; hence, some jobs may be rejected. A mixed integer linear programming model with the objective of maximizing the total profit gained from scheduled jobs is introduced. Since the problem is NP-hard and difficult to find an optimal solution in a reasonable computational time, an efficient genetic algorithm is presented as the solution procedure. A heuristic mechanism is proposed to use in each generation of the genetic algorithms to assure the feasibility and superior quality of the obtained solutions. Computational results show that the presented approach performs considerably in terms of both quality of solutions and required runtimes.     

带准备时间的柔性流水车间多序列有限缓冲区排产优化问题

针对带准备时间的柔性流水车间多序列有限缓冲区排产优化问题,提出一种改进的紧致遗传算法（Improved compactgenetic algorithm,ICGA）与局部指派规则结合的方法来解决该问题。全局优化过程采用改进的紧致遗传算法,为了克服紧致遗传算法（Compact genetic algorithm,CGA）易早熟收敛的问题,提出一种基于高斯映射的概率模型更新方式,在保持紧致遗传算法快速收敛特性的前提下,扩展了种群中个体的多样性,增强了算法进化活力。为减少生产阻塞和降低准备时间对排产过程的影响,设计了多种局部启发式规则来指导工件进出多序列有限缓冲区的分配和选择过程。采用某客车制造企业中的实例数据进行测试,测试结果表明,改进的紧致遗传算法与局部指派规则配合使用,能够有效解决带准备时间的柔性流水车间多序列有限缓冲区排产优化问题。