A review and classification on distributed permutation flowshop scheduling problems

The Distributed Permutation Flowshop Scheduling (DPFS) problem is one of the fastest-growing topics in the scheduling literature, which in turn is among the most prolific fields in Operational Research (OR). Although the problem has been formally stated only twelve years ago, the number of papers on the topic is growing at a rapid pace, and the rising interest –both from academics and practitioners– on distributed manufacturing paradigms seems to indicate that this trend will continue to increase. Possibly as a side effect of this steady growth, the state-of-the-art on many decision problems within the field is far from being clear, with substantial overlaps in the solution procedures, lack of (fair) comparisons against existing methods, or the use of different denominations for the same problem, among other issues. In this paper, we carry out a review of the DPFS literature aimed at providing a classification and notation for DPFS problems under a common framework. Within this framework, contributions are exhaustively presented and discussed, together with the state-of-the-art of the problems and lines for future research.     

A combined branch-and-bound and genetic algorithm based approach for a flowshop scheduling problem

In this paper, we study the application of a meta-heuristic to a two-machine flowshop scheduling problem. The meta-heuristic uses a branch-and-bound procedure to generate some information, which in turn is used to guide a genetic algorithm's search for optimal and near-optimal solutions. The criteria considered are makespan and average job flowtime. The problem has applications in flowshop environments where management is interested in reducing turn-around and job idle times simultaneously. We develop the combined branch-and-bound and genetic algorithm based procedure and two modified versions of it. Their performance is compared with that of three algorithms: pure branch-and-bound, pure genetic algorithm, and a heuristic. The results indicate that the combined approach and its modified versions are better than either of the pure strategies as well as the heuristic algorithm.     

A new constructive heuristic for the flowshop scheduling problem

This paper presents a simple constructive heuristic (HFC) for the flowshop makespan problem which is capable of producing non-permutation schedules when it deems it appropriate. HFC determines the order of any two jobs in the final schedule based on their order in all two-machine problems embedded in the problem. Computational experiments indicate that HFC performs as well as NEH which is the currently best available constructive heuristic on problems where a permutation schedule is expected to be optimal. However, HFC outperforms NEH on problems where a non-permutation schedule may be optimal.     

A partial enumeration heuristic for multi-objective flowshop scheduling problems

This paper addresses the flowshop scheduling problem with multiple performance objectives in such a way as to provide the decision maker with approximate Pareto optimal solutions. It is well known that the partial enumeration constructive heuristic NEH and its adaptations perform well for single objectives such as makespan, total tardiness and flowtime. In this paper, we develop a similar heuristic using the concept of Pareto dominance when comparing partial and complete schedules. The heuristic is tested on problems involving combinations of the above criteria. For the two-machine case, and the pairs of objectives: (i) makespan and maximum tardiness, (ii) makespan and total tardiness, the heuristic is compared with branch-and-bound algorithms proposed in the literature. For two and more than two machines, and the criteria combinations considered in this article, the heuristic performance is tested against constructive heuristics reported in the literature. By means of an illustrative example, it is shown that a genetic algorithm from the literature performs better when starting from heuristic solutions rather than random solutions.     

A parallel competitive colonial algorithm for JIT flowshop scheduling

This paper proposes two parallel algorithms which are improved by heuristics for a bi-objective flowshop scheduling problem with sequence-dependent setup times in a just-in-time environment. In the proposed algorithms, the population will be decomposed into the several sub-populations in parallel. Multiple objectives are combined with min–max method then each sub-population evolves separately in order to obtain a good approximation of the Pareto-front. After unifying the obtained results, we propose a variable neighborhood algorithm and a hybrid variable neighborhood search/tabu search algorithm to improve the Pareto-front. The non-dominated sets obtained from our proposed algorithms, a genetic local search and restarted iterated Pareto greedy algorithm are compared. It is found that most of the solutions in the net non-dominated front are yielded by our proposed algorithms.     

A discrete particle swarm optimization for lot-streaming flowshop scheduling problem

We consider an n-job, m-machine lot-streaming problem in a flowshop with equal-size sublots where the objective is to minimize the total weighted earliness and tardiness. To solve this problem, we first propose a so-called net benefit of movement (NBM) algorithm, which is much more efficient than the existing linear programming model for obtaining the optimal starting and completion times of sublots for a given job sequence. A new discrete particle swarm optimization (DPSO) algorithm incorporating the NBM algorithm is then developed to search for the best sequence. The new DPSO improves the existing DPSO by introducing an inheritance scheme, inspired by a genetic algorithm, into particles construction. To verify the proposed DPSO algorithm, comparisons with the existing DPSO algorithm and a hybrid genetic algorithm (HGA) are made. Computational results show that the proposed DPSO algorithm with a two-point inheritance scheme is very competitive for the lot-streaming flowshop scheduling problem.     

A bicriteria flowshop scheduling with a learning effect

In many situations, a worker’s ability improves as a result of repeating the same or similar tasks; this phenomenon is known as the learning effect. In this paper the learning effect is considered in a two-machine flowshop. The objective is to find a sequence that minimizes a weighted sum of total completion time and makespan. Total completion time and makespan are widely used performance measures in scheduling literature. To solve this scheduling problem, an integer programming model with n² + 6n variables and 7n constraints where n is the number of jobs is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, the problem with up to 30 jobs can be solved. A heuristic algorithm and a tabu search based heuristic algorithm are presented to solve large size problems. Experimental results show that the proposed heuristic methods can solve this problem with up to 300 jobs rapidly. According to the best of our knowledge, no work exists on the bicriteria flowshop with a learning effect.     

A scatter search algorithm for the distributed permutation flowshop scheduling problem

The distributed permutation flowshop problem has been recently proposed as a generalization of the regular flowshop setting where more than one factory is available to process jobs. Distributed manufacturing is a common situation for large enterprises that compete in a globalized market. The problem has two dimensions: assigning jobs to factories and scheduling the jobs assigned to each factory. Despite being recently introduced, this interesting scheduling problem has attracted attention and several heuristic and metaheuristic methods have been proposed in the literature. In this paper we present a scatter search (SS) method for this problem to optimize makespan. SS has seldom been explored for flowshop settings. In the proposed algorithm we employ some advanced techniques like a reference set made up of complete and partial solutions along with other features like restarts and local search. A comprehensive computational campaign including 10 existing algorithms, together with statistical analyses, shows that the proposed scatter search algorithm produces better results than existing algorithms by a significant margin. Moreover all 720 known best solutions for this problem are improved.     

Cooperative metaheuristics for the permutation flowshop scheduling problem

In this work, we propose cooperative metaheuristic methods for the permutation flowshop scheduling problem considering two objectives separately: total tardiness and makespan. We use the island model where each island runs an instance of the algorithm and communications start when the islands have reached certain level of evolution, that is, communication is not allowed from the beginning of the execution. Subsequent ones occur when new better solutions are found. We carry out an exhaustive comparison of the cooperative methods against the sequential counterparts running in completely comparable scenarios. Results have been carefully analysed by means of statistical procedures and we can conclude that the cooperative methods yield much better results than the sequential algorithms and state-of-the-art methods running in the same number of processors but without communications. The proposed cooperative schemes are easy to apply to other algorithms and problems.     

Group scheduling in a two-stage flowshop

This paper investigates a two-stage flowshop group scheduling problem with the objective of minimising makespan (the completion time of the last job). In the multiple-stage group scheduling, each job is generally classified into one family by considering its characteristics at all stages as a whole. However, in this study, each job is classified into multiple families, one family per stage. For this problem, two heuristics based on the branch-and-bound algorithm are constructed and their efficiencies are investigated.     

A bicriteria m-machine flowshop scheduling with sequence-dependent setup times

In this study, a bicriteria m-machine flowshop scheduling with sequence-dependent setup times is considered. The objective function of the problem is minimization of the weighted sum of total completion time and makespan. Only small size problems with up to 6 machines and 18 jobs can be solved by the proposed integer programming model. Also the model is tested on an example. We also proposed three heuristic approaches for solving large jobs problems. To solve the large sizes problems up to 100 jobs and 10 machines, special heuristics methods is used. Results of computational tests show that the proposed model is effective in solving problems.     

A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem

This paper considers an m-machine permutation flowshop scheduling problem of minimizing the makespan. This classical scheduling problem is still important in modern manufacturing systems, and is well known to be intractable (i.e., NP-hard). In fact branch-and-bound algorithms developed so far for this problem have not come to solve large scale problem instances with over a hundred jobs. In order to improve the performance of branch-and-bound algorithms this paper proposes a new dominance relation by which the search load could be reduced, and notices that it is based on a sufficient precondition. This suggests that the dominance relation holds with high possibility even if the precondition approximately holds, thus being more realistic. The branch-and-bound algorithm proposed here takes advantage of this possibility for obtaining an optimal solution as early as possible in the branch-and-bound search. For this purpose this paper utilizes membership functions in the context of the fuzzy inference. Extensive numerical experiments that were executed through Monte Carlo simulations and benchmark tests show that the developed branch-and-bound algorithm can solve 3-machine problem instances with up to 1000 jobs with probability of over 99%, and 4-machine ones with up to 900 jobs with over 97%.     

A hybrid genetic local search algorithm for the permutation flowshop scheduling problem

Traditionally, the permutation flowshop scheduling problem (PFSP) was with the criterion of minimizing makespan. The permutation flowshop scheduling problem to minimize the total flowtime has attracted more attention from researchers in recent years. In this paper, a hybrid genetic local search algorithm is proposed to solve this problem with each of both criteria. The proposed algorithm hybridizes the genetic algorithm and a novel local search scheme that combines two local search methods: the Insertion Search (IS) and the Insertion Search with Cut-and-Repair (ISCR). It employs the genetic algorithm to do the global search and two local search methods to do the local search. Two local search methods play different roles in the search process. The Insertion Search is responsible for searching a small neighborhood while the Insertion Search with Cut-and-Repair is responsible for searching a large neighborhood. Furthermore, the orthogonal-array-based crossover operator is designed to enhance the GA’s capability of intensification. The experimental results show the advantage of combining the two local search methods. The performance of the proposed hybrid genetic algorithm is very competitive. For the PFSP with the total flowtime criterion, it improved 66 out of the 90 current best solutions reported in the literature in short-term search and it also improved all the 20 current best solutions reported in the literature in long-term search. For the PFSP with the makespan criterion, the proposed algorithm also outperforms the other three methods recently reported in the literature.     

On complexity of optimal recombination for flowshop scheduling problems

Under study is the complexity of optimal recombination for various flowshop scheduling problems with the makespan criterion and the criterion of maximum lateness. The problems are proved to be NP-hard, and a solution algorithm is proposed. In the case of a flowshop problem on permutations, the algorithm is shown to have polynomial complexity for “almost all” pairs of parent solutions as the number of jobs tends to infinity.     

Two-machine flowshop scheduling with availability constraints

The majority of the scheduling literature carries a common assumption that machines are available all the time. However, this availability assumption may not be true in real industry settings, since a machine may become unavailable during certain periods of time when, for instance, a machine breakdown or a preventive maintenance activity is scheduled. Although the problem is realistic and important, it is relatively new and unstudied. In this paper, we study the two-machine flowshop problem under the assumption that the unavailable time is known in advance. We assume that if a job cannot be finished before the next down period of a machine then the job will have to partially restart when the machine has become available again. We call our model semiresumable. Our model contains two important special cases: resumable where the job can be continued without any penalty and nonresumable where the job needs to totally restart. We study the problem where an availability constraint is imposed only on one machine as well as on both machines. We provide complexity analysis, develop a pseudo-polynomial dynamic programming algorithm to solve the problem optimally and also propose heuristic algorithms with an error bound analysis.     

Bicriterion scheduling in the two-machine flowshop

Bicriterion scheduling problems have attracted the attention of many researchers, especially in the past decade. Although more than fifty papers have been published on this topic, most studies done so far focus only on a single machine. In this paper, we extend the development to the two-machine case and present algorithms for the bicriterion of minimising makespan and number of tardy jobs and of makespan and total tardiness. Computational results are also presented.     

Nonpreemptive flowshop scheduling with machine dominance

Flowshop scheduling deals with processing a set of jobs through a set of machines, where all jobs have to pass among machines in the same order. With the exception of minimizing a makespan on two machines, almost all other flowshop problems in a general setup are known to be computationally intractable. In this paper we study special cases of flowshop defined by additional machine dominance constraints. These constraints impose certain relations among the job processing times on different machines and make the studied problems tractable.     

Two-machine flowshop scheduling problem with coupled-operations

This paper addresses a generalization of the coupled-operations scheduling problem in the context of a flow shop environment. We consider the two-machine scheduling problem with the objective of minimizing the makespan. Each job consists of a coupled-operation to be processed first on the first machine and a single operation to be then processed on the second machine. A coupled-operation contains two operations separated by an exact time delay. The single operation can start on the second machine only when the coupled-operation on the first machine is completed. We prove the NP-completeness of two restricted versions of the general problem, whereas we also exhibit several other well solvable cases.

     

带有运输且加工具有灵活性的无等待流水作业排序问题

研究一类带有运输且加工具有灵活性的两阶段无等待流水作业排序问题, 其中每阶段只有一台机器, 每个工件有两道工序需要依次在两台机器上加工, 工件在两台机器上的加工及两道工序之间不允许等待. 给出两种近似算法, 并分别分析其最坏情况界. 第一种算法是排列排序, 证明了最坏情况界不超过5/2; 第二种算法将工件按照两道工序加工时间之和的递增顺序排序, 证明其最坏情况界不超过2. 最后, 通过数值模拟比较算法的性能. 对问题中各参数取不同值的情况, 分别生成若干个实例, 用算法得到的解与最优解的下界作比值, 通过分析这些比值的最大值、最小值和平均值来比较上述两个算法的性能.     

A bi-criteria two-machine flowshop scheduling problem with a learning effect

This paper addresses a bi-criteria two-machine flowshop scheduling problem when the learning effect is present. The objective is to find a sequence that minimizes a weighted sum of the total completion time and the maximum tardiness. In this article, a branch-and-bound method, incorporating several dominance properties and a lower bound, is presented to search for the exact solution for small job-size problems. In addition, two heuristic algorithms are proposed to overcome the inefficiency of the branch-and-bound algorithm for large job-size problems. Finally, computational results for this problem are provided to evaluate the performance of the proposed algorithms.