•An exhaustive review of the Non-Permutation Flow-Shop Scheduling problem.•A comprehensive classification in terms of objective functions and the solution methods employed in the literature.•A ...compilation of problems that, modeled as PFS, do not ensure optimality.•A revision of the main experimental results.•A detailed description of future research lines and literature gaps.
The Non-Permutation Flow-Shop scheduling problem (NPFS) is a generalization of the traditional Permutation Flow-Shop scheduling problem (PFS) that allows changes in the job order on different machines. The flexibility that NPFS provides in models for industrial applications justifies its use despite its combinatorial complexity. The literature on this problem has expanded largely in the last decade, indicating that the topic is an active research area. This review is a contribution towards the rationalization of the developments in the field, organizing them in terms of the objective functions in the different variants of the problem. A schematic presentation of both theoretical and experimental results summarizes many of the main advances in the study of NPFS. Finally, we include a bibliometric analysis, showing the most promising lines of future development.
•New Constructive heuristic for both the PBFSP and the DBFSP.•Combination of IGA and ILS methods with two types of VNS.•A MILP model solved for small-sized instances.•The proposed methods are very ...effective.
We consider the NP-hard problem of scheduling n jobs in F identical parallel flow shops, each consisting of a series of m machines, and doing so with a blocking constraint. The applied criterion is to minimize the makespan, i.e., the maximum completion time of all the jobs in F flow shops (lines). The Parallel Flow Shop Scheduling Problem (PFSP) is conceptually similar to another problem known in the literature as the Distributed Permutation Flow Shop Scheduling Problem (DPFSP), which allows modeling the scheduling process in companies with more than one factory, each factory with a flow shop configuration. Therefore, the proposed methods can solve the scheduling problem under the blocking constraint in both situations, which, to the best of our knowledge, has not been studied previously. In this paper, we propose a mathematical model along with some constructive and improvement heuristics to solve the parallel blocking flow shop problem (PBFSP) and thus minimize the maximum completion time among lines. The proposed constructive procedures use two approaches that are totally different from those proposed in the literature. These methods are used as initial solution procedures of an iterated local search (ILS) and an iterated greedy algorithm (IGA), both of which are combined with a variable neighborhood search (VNS). The proposed constructive procedure and the improved methods take into account the characteristics of the problem. The computational evaluation demonstrates that both of them –especially the IGA– perform considerably better than those algorithms adapted from the DPFSP literature.
The problem of maximizing total early work in a two‐machine flow‐shop, in which n jobs are to be scheduled subject to a common due date d, has been recently studied in the scheduling literature. An ...O(n2d4) time dynamic programming algorithm was presented first for the weighted case, and then for the unweighted case another O(n2d2) running time dynamic programming algorithm was proposed and converted into an On4ε2$$ O\left(\frac{n^4}{\varepsilon^2}\right) $$ time fully polynomial time approximation scheme (FPTAS). By establishing new problem properties, we present an O(nd2) time dynamic programming algorithm and an On3ε2$$ O\left(\frac{n^3}{\varepsilon^2}\right) $$ time FPTAS for the unweighted problem. We generalize the problem to a distributed setting of m parallel two‐machine flow‐shops, develop an O(nd3m) time dynamic programming algorithm, an On3m+1ε3m$$ O\left(\frac{n^{3m+1}}{\varepsilon^{3m}}\right) $$ time FPTAS, and three integer linear programming (ILP) formulations for it. Computational experiments are conducted to appraise the proposed ILP models.
To meet the multi-cooperation production demand of enterprises, the distributed permutation flow shop scheduling problem (DPFSP) has become the frontier research in the field of manufacturing ...systems. In this paper, we investigate the DPFSP by minimizing a makespan criterion under the constraint of sequence-dependent setup times. To solve DPFSPs, significant developments of some metaheuristic algorithms are necessary. In this context, a simple and effective improved iterated greedy (NIG) algorithm is proposed to minimize makespan in DPFSPs. According to the features of DPFSPs, a two-stage local search based on single job swapping and job block swapping within the key factory is designed in the proposed algorithm. We compare the proposed algorithm with state-of-the-art algorithms, including the iterative greedy algorithm (2019), iterative greedy proposed by Ruiz and Pan (2019), discrete differential evolution algorithm (2018), discrete artificial bee colony (2018), and artificial chemical reaction optimization (2017). Simulation results show that NIG outperforms the compared algorithms.
The hybrid flow shop scheduling problem Ruiz, Rubén; Vázquez-Rodríguez, José Antonio
European journal of operational research,
08/2010, Letnik:
205, Številka:
1
Journal Article
Recenzirano
Odprti dostop
The scheduling of flow shops with multiple parallel machines per stage, usually referred to as the hybrid flow shop (HFS), is a complex combinatorial problem encountered in many real world ...applications. Given its importance and complexity, the HFS problem has been intensively studied. This paper presents a literature review on exact, heuristic and metaheuristic methods that have been proposed for its solution. The paper briefly discusses and reviews several variants of the HFS problem, each in turn considering different assumptions, constraints and objective functions. Research opportunities in HFS are also discussed.
•An iterated greedy algorithm for the total tardiness parallel blocking flow shop problem.•Constructive heuristics which considers the characteristics of the problem.•Design of experiments to ...calibrate and select the best variant.
This paper proposes an iterated greedy algorithm for scheduling jobs in F parallel flow shops (lines), each consisting of a series of m machines without storage capacity between machines. This constraint can provoke the blockage of machines if a job has finished its operation and the next machine is not available. The criterion considered is the minimization of the sum of tardiness of all the jobs to schedule, i.e., minimization of the total tardiness of jobs. Notice that the proposed method is also valid for solving the Distributed Permutation Blocking Flow Shop Scheduling Problem (DBFSP), which allows modelling the scheduling process in companies with more than one factory when each factory has an identical flow shop configuration. Firstly, several constructive procedures have been implemented and tested to provide an efficient solution in terms of quality and CPU time. This initial solution is later improved upon with an iterated greedy algorithm that includes a variable neighbourhood search for interchanging or reassigning jobs from the critical line to other lines. Next, two strategies have been tested for selecting the critical line; the one with a higher total tardiness of jobs and the one with a job that has the highest tardiness. The experimental design chooses the best combination of initial solution and critical line selection. Finally, we compare the performance of the proposed algorithm against other benchmark algorithms proposed for the DPFSP, which have been adapted to the problem being considered here since, to the best of our knowledge, this is the first attempt to solve either the Parallel Blocking Flow Shop problem or the Distributed Blocking Flow Shop problem with the goal of minimizing total tardiness. This comparison has allowed us to confirm the good performance of the proposed method.
•Effective heuristic for the parallel blocking flow shop problem with setup times.•Performance evaluation of different neighbourhood structures and local searches.•Performance evaluation of different ...initial solution procedures.•The best performing constructive method does not lead to obtaining better solutions.•The level of setup times has slightly influence on the behavior of heuristics.
This paper deals with the problem of scheduling jobs in a parallel flow shop configuration under the blocking constraint, in which the setup time of machines depends not only on the job to be processed but also on the previously processed one, i.e., there are sequence-dependent setup times. The performance analysis of several iterated greedy algorithms with different initial solution procedures and local searches lets us define an efficient algorithm to minimize the maximum job completion time. Moreover, the computational evaluation showed the efficiency of searching in different neighborhood structures and noted the significant influence of the initial solution. However, contrary to other scheduling problems, starting with a high quality solution does not guarantee better performance of the algorithm.
In this paper, an effective estimation of distribution algorithm (EDA) is proposed to solve the distributed permutation flow-shop scheduling problem (DPFSP). First, the earliest completion factory ...rule is employed for the permutation based encoding to generate feasible schedules and calculate the schedule objective value. Then, a probability model is built for describing the probability distribution of the solution space, and a mechanism is provided to update the probability model with superior individuals. By sampling the probability model, new individuals can be generated among the promising search region. Moreover, to enhance the local exploitation, some local search operators are designed based on the problem characteristics and utilized for the promising individuals. In addition, the influence of parameter setting of the EDA is investigated based on the Taguchi method of design of experiments, and a suitable parameter setting is suggested. Finally, numerical simulations based on 420 small-sized instances and 720 large-sized instances are carried out. The comparative results with some existing algorithms demonstrate the effectiveness of the proposed EDA in solving the DPFSP. In addition, the new best-known solutions for 17 out of 420 small instances and 589 out of 720 large instances are found.
PDF
