A genetic algorithm for flow shop scheduling problems

Many scheduling problems are NP-hard problems. For such NP-hard combinatorial optimization problems, heuristics play a major role in searching for near-optimal solutions. In this paper we develop a genetic algorithm-based heuristic for the flow shop scheduling problem with makespan as the criterion. The performance of the algorithm is compared with the established NEH algorithm. Computational experience indicates that genetic algorithms can be good techniques for flowshop scheduling problems.     

Bilevel programming approach applied to the flow shop scheduling problem under fuzziness

This paper presents a fuzzy bilevel programming approach to solve the flow shop scheduling problem. The problem considered here differs from the standard form in that operators are assigned to the machines and imposing a hierarchy of two decision makers with fuzzy processing times. The shop owner considered higher level and assigns the jobs to the machines in order to minimize the flow time while the customer is the lower level and decides on a job schedule in order to minimize the makespan. In this paper, we use the concepts of tolerance membership function at each level to define a fuzzy decision model for generating optimal (satisfactory) solution for bilevel flow shop scheduling problem. A solution algorithm for solving this problem is given. Mathematics Subject Classification: 90C70, 90B36, 90C99     

Solving multi-criteria scheduling flow shop problem through compromise programming and satisfaction functions

The multi-criteria scheduling problem is one of the main research subjects in the field of multiple objectives programming. Several procedures have been developed to deal with this type of problem where some conflicting criteria have to be optimized simultaneously. The aim of our paper is to propose an aggregation procedure that integrates three different criteria to find the best sequence in a flow shop production environment. The compromise programming model and the concept of satisfaction functions will be utilized to integrate explicitly the manager’s preferences according to the deviations between the achievement and the aspiration levels of the following criteria: Makespan, total flow time and total tardiness.     

Approximability of flow shop scheduling

Shop scheduling problems are notorious for their intractability, both in theory and practice. In this paper, we construct a polynomial approximation scheme for the flow shop scheduling problem with an arbitrary fixed number of machines. For the three common shop models (open, flow, and job), this result is the only known approximation scheme. Since none of the three models can be approximated arbitrarily closely in the general case (unless P = NP), the result demonstrates the approximability gap between the models in which the number of machines is fixed, and those in which it is part of the input of the instance. The result can be extended to flow shops with job release dates and delivery times and to flow shops with a fixed number of stages, where the number of machines at any stage is fixed. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper appeared in theProceedings of the 36th Annual IEEE Symposium on the Foundations of Computer Science, 1995.Research supported by NSF grant DMI-9496153.     

Outsourcing and scheduling for two-machine ordered flow shop scheduling problems

This paper considers a two-machine ordered flow shop problem, where each job is processed through the in-house system or outsourced to a subcontractor. For in-house jobs, a schedule is constructed and its performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and the total outsourcing cost. Since this problem is NP-hard, we present an approximation algorithm. Furthermore, we consider three special cases in which job j has a processing time requirement p_j, and machine i a characteristic q_i. The first case assumes the time job j occupies machine i is equal to the processing requirement divided by a characteristic value of machine i, that is, p_j/q_i. The second (third) case assumes that the time job j occupies machine i is equal to the maximum (minimum) of its processing requirement and a characteristic value of the machine, that is, max{p_j, q_i} (min{p_j, q_i}). We show that the first and the second cases are NP-hard and the third case is polynomially solvable.     

Stochastic flow shop scheduling model for the Panama Canal

Reducing transit time is becoming increasingly important in maritime shipping of manufactured goods and commodities. Traversing the Panama Canal is a principal component of many global companies’ strategies to reduce shipping time in their supply chain. Operations in the Panama Canal can be described by a capacitated queueing network. In this study we used a metaheuristic approach based on Nested Partitions to find near optimal schedules for daily vessel traffic consisting of large vessels that want to pass through the Panama Canal. Results indicate that the metaheuristic technique consistently reduced the makespan of a set of vessels as compared to historical schedules used in canal operations. We also found distinct patterns in the schedules in which certain vessels consistently appeared at a certain position in the schedule.     

Bounding strategies for the hybrid flow shop scheduling problem

In this paper, we investigate new lower and upper bounds for the multiple-center hybrid flow shop scheduling problem. We propose a family of center-based lower bounds as well as a destructive lower bound that is based on the concept of revised energetic reasoning. Also, we describe an optimization-based heuristic that requires iteratively solving a sequence of parallel machine problems with heads and tails. We present the results of extensive computational experiments that provide evidence that the proposed bounding procedures consistently improve the best existing ones.     

Analysis of flow shop scheduling anomalies

Anomalies in flow shop scheduling are rare; only two anomalies have been reported. We present five new anomalies for the permutation flow shop models with the minimum makespan objective and seven more anomalies for the minimum total flow time objective. These anomalies (including the existing ones) are divided into three types corresponding to an increased processing time of a single operation, the addition of a job and the addition of a machine. We derive two properties which, when satisfied, eliminate the possibility of certain anomalies. We conclude that restrictions such as no-delay schedules, no job waiting or no machine idle time (after it starts processing) often result in anomalies. We also show that anomalies can also occur in non-permutation flow shops (four new anomalies presented).     

A hybrid genetic algorithm for the job shop scheduling problem

This paper presents a hybrid genetic algorithm for the job shop scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a schedule is obtained a local search heuristic is applied to improve the solution. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm.     

A tabu-search heuristic for the flexible-resource flow shop scheduling problem

This paper presents a tabu-search heuristic for the flexible-resource flow shop scheduling (FRFS) problem [7]. The FRFS problem generalizes the classic flow shop scheduling problem by allowing job-operation processing times to depend on the amount of resource assigned to an operation; the objective is to determine simultaneously the job sequence, resource-allocation policy, and operation start times that optimize system performance. The tabu-search heuristic (TSH) employs a nested-search strategy based on a decomposition of the FRFS problem into these three components. We discuss computational experience with the THS procedure on more than 1600 test problems. The results show that TSH is effective in obtaining near-optimal solutions to the FRFS test problems. In particular, TSH generates optimal solutions for more than 70% of the test problems for which optimal solutions are known; overall, these solutions are within 0.3% of optimality on the average, and within 2.5% of optimality in the worst case.This research was supported in part by National Science Foundation grant SES90-22940.     

A note of using effective immune based approach for the flow shop scheduling with buffers

This note considers flow shop scheduling with buffers. The objective is to minimize the makespan. As we know, such a problem has several applications in manufacturing and has gained wide attention both in academic and engineering fields. In this note, we propose an immune based approach (IA) to solve this NP-hard problem. Numerical results of 29 benchmark problems from the OR-Library are reported and compared with those of a hybrid genetic algorithm (HGA). As shown, the proposed IA is effective and robust. The solutions by proposed IA are superior to those of HGA reported in the literature. In addition, the average of the relative errors of the proposed IA is only 0.85% for 29 instances with infinite buffers. Limited numerical results show that, as expected, buffer size has a great impact on the scheduling objective especially for larger-scale instances, and there are also significant differences with or without buffers for all instances. But the effect of increasing buffer size from 1 up to 2, 4 or ∞ decreases drastically for all instances.     

Local search algorithms for the multiprocessor flow shop scheduling problem

The multiprocessor flow shop scheduling problem is a generalization of the ordinary flow shop scheduling problem. The problem consists of both assigning operations to machines and scheduling the operations assigned to the same machine. We review the literature on local search methods for flow shop and job shop scheduling and adapt them to the multiprocessor flow shop scheduling problem. Other local search approaches we consider are variable-depth search and simulated annealing. We show that tabu search and variable-depth search with a neighborhood originated by Nowicki and Smutnicki outperform the other algorithms.     

On non-permutation solutions to some two machine flow shop scheduling problems

In this paper, we study two versions of the two machine flow shop scheduling problem, where schedule length is to be minimized. First, we consider the two machine flow shop with setup, processing, and removal times separated. It is shown that an optimal solution need not be a permutation schedule, and that the problem isNP-hard in the strong sense, which contradicts some known results. The tight worst-case bound for an optimal permutation solution in proportion to a global optimal solution is shown to be 3/2. An O(n) approximation algorithm with this bound is presented. Secondly, we consider the two machine flow shop with finite storage capacity. Again, it is shown that there may not exist an optimal solution that is a permutation schedule, and that the problem isNP-hard in the strong sense.     

A local search method for permutation flow shop scheduling

It is well known that a local search method, a widely used approach for solving the permutation flow shop scheduling problem, can easily be trapped at a local optimum. In this paper, we propose two escape-from-trap procedures to move away from local optima. Computational experiments carried out on a standard set of instances show that this heuristic algorithm generally outperforms an effective approximation algorithm.     

On operators and search space topology in multi-objective flow shop scheduling

Multi-objective optimization using evolutionary algorithms identifies Pareto-optimal alternatives or their close approximation by means of a sequence of successive local improvement moves. While several successful applications to combinatorial optimization problems are known, studies of underlying problem structures are still scarce.     

A problem expanding parametric programming method for solving the job shop scheduling problem

A new zero-one integer programming model for the job shop scheduling problem with minimum makespan criterion is presented. The algorithm consists of two parts: (a) a branch and bound parametric linear programming code for solving the job shop problem with fixed completion time; (b) a problem expanding algorithm for finding the optimal completion time. Computational experience for problems having up to thirty-six operations is presented. The largest problem solved was limited by memory space, not computation time. Efforts are under way to improve the efficiency of the algorithm and to reduce its memory requirements.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University, under Contract No. N00014-82-K-0329 NR 047-048 with the U.S. Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

A comparison of local search methods for flow shop scheduling

Local search techniques are widely used to obtain approximate solutions to a variety of combinatorial optimization problems. Two important categories of local search methods are neighbourhood search and genetic algorithms. Commonly used neighbourhood search methods include descent, threshold accepting, simulated annealing and tabu search. In this paper, we present a computational study that compares these four neighbourhood search methods, a genetic algorithm, and a hybrid method in which descent is incorporated into the genetic algorithm. The performance of these six local search methods is evaluated on the problem of scheduling jobs in a permutation flow shop to minimize the total weighted completion time. Based on the results of extensive computational tests, simulated annealing is found to generate better quality solutions than the other neighborhood search methods. However, the results also indicate that the hybrid genetic descent algorithm is superior to simulated annealing.     

A contribution to the stochastic flow shop scheduling problem

This paper deals with performance evaluation and scheduling problems in m machine stochastic flow shop with unlimited buffers. The processing time of each job on each machine is a random variable exponentially distributed with a known rate. We consider permutation flow shop. The objective is to find a job schedule which minimizes the expected makespan. A classification of works about stochastic flow shop with random processing times is first given. In order to solve the performance evaluation problem, we propose a recursive algorithm based on a Markov chain to compute the expected makespan and a discrete event simulation model to evaluate the expected makespan. The recursive algorithm is a generalization of a method proposed in the literature for the two machine flow shop problem to the m machine flow shop problem with unlimited buffers. In deterministic context, heuristics (like CDS [Management Science 16 (10) (1970) B630] and Rapid Access [Management Science 23 (11) (1977) 1174]) and metaheuristics (like simulated annealing) provide good results. We propose to adapt and to test this kind of methods for the stochastic scheduling problem. Combinations between heuristics or metaheuristics and the performance evaluation models are proposed. One of the objectives of this paper is to compare the methods together. Our methods are tested on problems from the OR-Library and give good results: for the two machine problems, we obtain the optimal solution and for the m machine problems, the methods are mutually validated.     

Heuristics for scheduling in a flow shop with multiple processors

This study investigates the performance of scheduling heuristics in a flow shop with multiple processors. We investigated five better performing flow shop heuristics for their performances of makespan and mean flow time criteria in a flow shop with multiple processors. The study examined the effects of problem characteristics (number of jobs, number of machine stages and number of parallel processors at each stage) and the performance of heuristics using regression analysis. We found that although structural characteristics explain most of the variation in performance, heuristics also had an effect. The experimental results showed that flow shop heuristics developed by Nawaz, Enscore, and Ham and that of Ho were comparable in performance in a flow shop with multiple processors. However, the former was slightly more consistent in results for both criteria.     

A novel parallel quantum genetic algorithm for stochastic job shop scheduling

In this paper, a Novel Parallel Quantum Genetic Algorithm (NPQGA) is proposed for the stochastic Job Shop Scheduling Problem with the objective of minimizing the expected value of makespan, where the processing times are subjected to independent normal distributions. Based on the parallel evolutionary idea and some concepts of quantum theory, we simulate a model of parallel quantum computation. In this frame, there are some demes (sub-populations) and some universes (groups of populations), which are structured in super star-shaped topologies. A new migration scheme based on penetration theory is developed to control migration rate and direction adaptively between demes, and a novel quantum crossover strategy is devised among universes. The quantum evolution is executed in every deme by applying some improvement operators (the coding mechanism aiming at job shop, the new quantum rotation angle and the catastrophe operator). Experiment results show NPQGA's effectiveness and applicability.