Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints

This paper presents a novel, two-level mixed-integer programming model of scheduling N jobs on M parallel machines that minimizes bi-objectives, namely the number of tardy jobs and the total completion time of all the jobs. The proposed model considers unrelated parallel machines. The jobs have non-identical due dates and ready times, and there are some precedence relations between them. Furthermore, sequence-dependent setup times, which are included in the proposed model, may be different for each machine depending on their characteristics. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches or optimization tools is extremely difficult. This paper proposes an efficient genetic algorithm (GA) to solve the bi-objective parallel machine scheduling problem. The performance of the presented model and the proposed GA is verified by a number of numerical experiments. The related results show the effectiveness of the proposed model and GA for small and large-sized problems.     

Algorithms for a realistic variant of flowshop scheduling

This paper deals with a realistic variant of flowshop scheduling, namely the hybrid flexible flowshop. A hybrid flowshop mixes the characteristics of regular flowshops and parallel machine problems by considering stages with parallel machines instead of having one single machine per stage. We also investigate the flexible version where stage skipping might occur, i.e., not all stages must be visited by all jobs. Lastly, we also consider job sequence dependent setup times per stage. The optimization criterion considered is makespan minimization. While many approaches for hybrid flowshops have been proposed, hybrid flexible flowshops have been rarely studied. The situation is even worse with the addition of sequence dependent setups. In this study, we propose two advanced algorithms that specifically deal with the flexible and setup characteristics of this problem. The first algorithm is a dynamic dispatching rule heuristic, and the second is an iterated local search metaheuristic. The proposed algorithms are evaluated by comparison against seven other high performing existing algorithms. The statistically sound results support the idea that the proposed algorithms are very competitive for the studied problem.     

Non-permutation flowshop scheduling with dual resources

Typically, in order to process jobs in a flowshop both machines and labor are required. However, in traditional scheduling problems, labor is assumed to be plentiful and only machine is considered to be a constraint. This assumption could be due to the lower cost of labor compared to machines or the complexity of dual-resource constrained problems. In this paper a mathematical model is developed to minimize the work-in-process inventory while maximizing the service level in a flowshop with dual resources. The model focuses on optimizing a non-permutation flowshop. There are different skill levels considered for labor and the setup times on machines are sequence-dependent. Jobs are allowed to skip one or more stages in the flowshop. Job release and machine availability times are considered to be dynamic. The problem is solved in two layers. The outer layer is a search algorithm to find the schedule of jobs on the machine (traditional flowshop scheduling problem) and the inner layer is a three-step heuristic to find a schedule of jobs on labor in accordance to the machine schedule. Three different search algorithms are developed to solve the proposed NP-hard problem. First algorithm can solve a permutation flowshop while the other two are developed to solve a non-permutation flowshop. The comparison between the optimal solution and the search algorithms in small examples shows a good performance of the algorithms with an average deviation of only 2.00%. An experimental design analyzes the effectiveness and efficiency of the algorithms statistically. The results show that non-permutation algorithms perform better than the permutation algorithm, although the former are less efficient. The effectiveness and efficiency in all three algorithms have an inverse relation. To the best of our knowledge, this research is the first of its kind to provide a comprehensive mathematical model for dual resource flowshop scheduling problem.     

Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness

In this paper, we address a new Lagrangian relaxation (LR) method for solving the hybrid flowshop scheduling problem to minimize the total weighted tardiness. For the conventional LR, the problem relaxing machine capacity constraints can be decomposed into individual job-level subproblems which can be solved by dynamic programming. The Lagrangian dual problem is solved by the subgradient method. In this paper, a Lagrangian relaxation with cut generation is proposed to improve the Lagrangian bounds for the conventional LR. The lower bound is strengthened by imposing additional constraints for the relaxed problem. The state space reductions for dynamic programming for subproblems are also incorporated. Computational results demonstrate that the proposed method outperforms the conventional LR method without significantly increasing the total computing time.     

Solving a bi-objective flowshop scheduling problem by a Multi-objective Immune System and comparing with SPEA2+ and SPGA

This paper presents a bi-objective flowshop scheduling problem with sequence-dependent setup times. The objective functions are to minimize the total completion time and the total earliness/tardiness for all jobs. An integer programming model is developed for the given problem that belongs to an NP-hard class. Thus, an algorithm based on a Multi-objective Immune System (MOIS) is proposed to find a locally Pareto-optimal frontier of the problem. To prove the efficiency of the proposed MOIS, different test problems are solved. Based on some comparison metrics, the computational results of the proposed MOIS is compared with the results obtained using two well-established multi-objective genetic algorithms, namely SPEA2+ and SPGA. The related results show that the proposed MOIS outperforms genetic algorithms, especially for the large-sized problems.     

Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints

One of the common assumptions in the field of scheduling is that machines are always available in the planning horizon. This may not be true in realistic problems since machines might be busy processing some jobs left from previous production horizon, breakdowns or preventive maintenance activities. Another common assumption is the consideration of setup times as a part of processing times, while in some industries, such as printed circuit board and automobile manufacturing, not only setups are an important factor but also setup magnitude of a job depends on its immediately preceding job on the same machine, known as sequence-dependent setup times. In this paper, we consider hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints caused by preventive maintenance. The optimization criterion is the minimization of makespan. Since this problem is NP-hard in the strong sense, we propose three heuristics, based on SPT, LPT and Johnson rule and two metaheuristics based on genetic algorithm and simulated annealing. Computational experiments are performed to evaluate the efficiencies of the algorithms.     

An iterated local search for the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times

Due to its simplicity yet powerful search ability, iterated local search (ILS) has been widely used to tackle a variety of single-objective combinatorial optimization problems. However, applying ILS to solve multi-objective combinatorial optimization problems is scanty. In this paper we design a multi-objective ILS (MOILS) to solve the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times to minimize the makespan and total weighted tardiness of all jobs. In the MOILS, we design a Pareto-based variable depth search in the multi-objective local search phase. The search depth is dynamically adjusted during the search process of the MOILS to strike a balance between exploration and exploitation. We incorporate an external archive into the MOILS to store the non-dominated solutions and provide initial search points for the MOILS to escape from local optima traps. We compare the MOILS with several multi-objective evolutionary algorithms (MOEAs) shown to be effective for treating the multi-objective permutation flowshop scheduling problem in the literature. The computational results show that the proposed MOILS outperforms the MOEAs.     

A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers

This paper investigates the hybrid flowshop scheduling with finite intermediate buffers, whose objective is to minimize the sum of weighted completion time of all jobs. Since this problem is very complex and has been proven strongly NP-hard, a tabu search heuristic is proposed. In this heuristic there are two main features. One is that a scatter search mechanism is incorporated to improve the diversity of the search procedure. And the other is that a permutation of N jobs representing their processing order in the first stage instead of a complex complete schedule is used to denote a solution. Computational experiments on randomly generated instances with different structures show that the proposed tabu search heuristic can provide good solutions compared to both the lower bounds and the algorithm proposed for this problem in a lately published literature.     

A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times

This paper presents a hybrid approach based on the integration between a genetic algorithm (GA) and concepts from constraint programming, multi-objective evolutionary algorithms and ant colony optimization for solving a scheduling problem. The main contributions are the integration of these concepts in a GA crossover operator. The proposed methodology is applied to a single machine scheduling problem with sequence-dependent setup times for the objective of minimizing the total tardiness. A sensitivity analysis of the hybrid approach is carried out to compare the performance of the GA and the hybrid genetic algorithm (HGA) approaches on different benchmarks from the literature. The numerical experiments demonstrate the HGA efficiency and effectiveness which generates solutions that approach those of the known reference sets and improves several lower bounds.     

Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—Variable neighborhood search approach

In scheduling problems, taking the sequence-dependent setup times into account is one of the important issues that have recently been considered by researchers in the production scheduling field. In this paper, we consider flexible job-shop scheduling problem (FJSP) with sequence-dependent setup times to minimize makespan and mean tardiness. The FJSP consists of two sub-problems from which the first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on all machines. To solve this problem, a variable neighborhood search (VNS) algorithm based on integrated approach is proposed. In the presented optimization method, the external loop controlled the stop condition of algorithm and the internal loop executed the search process. To search the solution space, the internal loop used two main search engines, i.e. shake and local search procedures. In addition, neighborhood structures related to the sequencing problem and the assignment problem were employed to generate neighboring solutions. To evaluate the performance of the proposed algorithm, 20 test problems in different sizes are randomly generated. Consequently, computational results and comparisons validate the quality of the proposed approach.     

A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time

We investigate the problem of scheduling n jobs in s-stage hybrid flowshops with parallel identical machines at each stage. The objective is to find a schedule that minimizes the sum of weighted completion times of the jobs. This problem has been proven to be NP-hard. In this paper, an integer programming formulation is constructed for the problem. A new Lagrangian relaxation algorithm is presented in which precedence constraints are relaxed to the objective function by introducing Lagrangian multipliers, unlike the commonly used method of relaxing capacity constraints. In this way the relaxed problem can be decomposed into machine type subproblems, each of which corresponds to a specific stage. A dynamic programming algorithm is designed for solving parallel identical machine subproblems where jobs may have negative weights. The multipliers are then iteratively updated along a subgradient direction. The new algorithm is computationally compared with the commonly used Lagrangian relaxation algorithms which, after capacity constraints are relaxed, decompose the relaxed problem into job level subproblems and solve the subproblems by using the regular and speed-up dynamic programming algorithms, respectively. Numerical results show that the new Lagrangian relaxation method produces better schedules in much shorter computation time, especially for large-scale problems.     

Complexity and algorithms for two-stage flexible flowshop scheduling with availability constraints

This paper considers the two-stage flexible flowshop scheduling problem with availability constraints. We discuss the complexity and the approximability of the problem, and provide some approximation algorithms with finite and tight worst case performance bounds for some special cases of the problem.     

A Self-guided Genetic Algorithm for permutation flowshop scheduling problems

In this paper we develop a Self-guided Genetic Algorithm (Self-guided GA), which belongs to the category of Estimation of Distribution Algorithms (EDAs). Most EDAs explicitly use the probabilistic model to sample new solutions without using traditional genetic operators. EDAs make good use of the global statistical information collected from previous searches but they do not efficiently use the location information about individual solutions. It is recently realized that global statistical information and location information should complement each other during the evolution process. In view of this, we design the Self-guided GA based on a novel strategy to combine these two kinds of information. The Self-guided GA does not sample new solutions from the probabilistic model. Instead, it estimates the quality of a candidate offspring based on the probabilistic model used in its crossover and mutation operations. In such a way, the mutation and crossover operations are able to generate fitter solutions, thus improving the performance of the algorithm. We tested the proposed algorithm by applying it to deal with the NP-complete flowshop scheduling problem to minimize the makespan. The experimental results show that the Self-guided GA is very promising. We also demonstrate that the Self-guided GA can be easily extended to treat other intractable combinatorial problems.     

Robust scheduling on a single machine to minimize total flow time

In a real-world manufacturing environment featuring a variety of uncertainties, production schedules for manufacturing systems often cannot be executed exactly as they are developed. In these environments, schedule robustness that guarantees the best worst-case performance is a more appropriate criterion in developing schedules, although most existing studies have developed optimal schedules with respect to a deterministic or stochastic scheduling model. This study concerns robust single machine scheduling with uncertain job processing times and sequence-dependent family setup times explicitly represented by interval data. The objective is to obtain robust sequences of job families and jobs within each family that minimize the absolute deviation of total flow time from the optimal solution under the worst-case scenario. We prove that the robust single machine scheduling problem of interest is NP-hard. This problem is reformulated as a robust constrained shortest path problem and solved by a simulated annealing-based algorithmic framework that embeds a generalized label correcting method. The results of numerical experiments demonstrate that the proposed heuristic is effective and efficient for determining robust schedules. In addition, we explore the impact of degree of uncertainty on the performance measures and examine the tradeoff between robustness and optimality.     

A multi-objective electromagnetism algorithm for a bi-objective flowshop scheduling problem

This paper deals with a bi-objective flowshop scheduling problem minimizing the makespan and total weighted tardiness, in which all jobs may not be processed by all machines. Furthermore, we consider transportation times between machines. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using traditional approaches and optimization tools is extremely difficult. This paper presents a new multi-objective electromagnetism algorithm (MOEM). The motivation behind this algorithm has risen from the attraction–repulsion mechanism of electromagnetic theories. Along with MOEA, we apply simulated annealing to solve the given problem. A set of experimental instances are carried out to evaluate the algorithm by advanced multi-objective performance measures. The related results show that a variant of our proposed MOEM provides sound performance comparing with other algorithms.     

A hybrid artificial immune algorithm for a realistic variant of job shops to minimize the total completion time

This paper investigates an extended problem of job shop scheduling to minimize the total completion time. With aim of actualization of the scheduling problems, many researchers have recently considered realistic assumptions in their problems. Two of the most applied assumptions are to consider sequence-dependent setup times and machine availability constraints (MACs). In this paper, we deal with a specific case of MACs caused by preventive maintenance (PM) operations. Contrary to the previous papers considering fixed or/and conservative policies, we consider flexible PM operations, in which PM operations may be postponed or expedited as required. A simple technique is employed to schedule production jobs along with the flexible MACs caused by PM. To solve the given problem, we present a novel meta-heuristic method based on the artificial immune algorithm (AIA) incorporating some advanced features. For further enhancement, the proposed AIA is hybridized with a simple and fast simulated annealing (SA). To evaluate the proposed algorithms, we compare our proposed AIA with three well-known algorithms taken from the literature. Finally, we find that the proposed AIA outperforms other algorithms.     

A hybrid flowshop scheduling model considering dedicated machines and lot-splitting for the solar cell industry

This paper studies a solar cell industry scheduling problem, which is similar to traditional hybrid flowshop scheduling (HFS). In a typical HFS problem, the allocation of machine resources for each order should be scheduled in advance. However, the challenge in solar cell manufacturing is the number of machines that can be adjusted dynamically to complete the job. An optimal production scheduling model is developed to explore these issues, considering the practical characteristics, such as hybrid flowshop, parallel machine system, dedicated machines, sequence independent job setup times and sequence dependent job setup times. The objective of this model is to minimise the makespan and to decide the processing sequence of the orders/lots in each stage, lot-splitting decisions for the orders and the number of machines used to satisfy the demands in each stage. From the experimental results, lot-splitting has significant effect on shortening the makespan, and the improvement effect is influenced by the processing time and the setup time of orders. Therefore, the threshold point to improve the makespan can be identified. In addition, the model also indicates that more lot-splitting approaches, that is, the flexibility of allocating orders/lots to machines is larger, will result in a better scheduling performance.     

The distributed permutation flowshop scheduling problem

This paper studies a new generalization of the regular permutation flowshop scheduling problem (PFSP) referred to as the distributed permutation flowshop scheduling problem or DPFSP. Under this generalization, we assume that there are a total of F identical factories or shops, each one with m machines disposed in series. A set of n available jobs have to be distributed among the F factories and then a processing sequence has to be derived for the jobs assigned to each factory. The optimization criterion is the minimization of the maximum completion time or makespan among the factories. This production setting is necessary in today's decentralized and globalized economy where several production centers might be available for a firm. We characterize the DPFSP and propose six different alternative mixed integer linear programming (MILP) models that are carefully and statistically analyzed for performance. We also propose two simple factory assignment rules together with 14 heuristics based on dispatching rules, effective constructive heuristics and variable neighborhood descent methods. A comprehensive computational and statistical analysis is conducted in order to analyze the performance of the proposed methods.     

Scheduling a hybrid flowshop with batch production at the last stage

In this paper, we address the problem of scheduling n$n$ jobs in an s$s$-stage hybrid flowshop with batch production at the last stage with the objective of minimizing a given criterion with respect to the completion time. The batch production at stage s$s$ is referred to as serial batches by Hopp and Spearman where the processing time of a batch is equal to the sum of the processing times of all jobs included in it. This paper establishes an integer programming model and proposes a batch decoupling based Lagrangian relaxation algorithm for this problem. In this algorithm, after capacity constraints are relaxed by Lagrangian multipliers, the relaxed problem is decomposed based on a batch, unlike the commonly used job decoupling, so that it can be decomposed into batch-level subproblems, each for a specific batch. An improved forward dynamic programming algorithm is then designed for solving these subproblems where all operations within a batch form an in-tree structure and the precedence relations exist not only between the operations of a job but between the jobs in this batch at the last stage. A computational comparison is provided for the developed algorithm and the commonly used Lagrangian relaxation algorithm which, after capacity constraints and precedence relations within a batch are relaxed, decomposes the relaxed problem into job-level subproblems and solves the subproblems by using dynamic programming. Numerical results show that the designed Lagrangian relaxation method provides much better schedules and converges faster for small to medium sized problems, especially for larger sized problems.     

Heuristics and metaheuristics for mixed blocking constraints flowshop scheduling problems

Storage or buffer capacities between successive machines in flowshop problems may be unlimited, limited or null. The last two cases can lead to blocking situations. In flowshop scheduling literature, many studies have been performed about classical flowshop problems and also about some problems with only one blocking situation between all machines.