In this paper it is presented an improvement of the branch and bound algorithm for the permutation flow shop problem with blocking-in-process and setup times with the objective of minimizing the total flow time and tardiness, which is known to be NP-Hard when there are two or more machines involved. With that objective in mind, a new machine-based lower bound that exploits some structural properties of the problem. A database with 27 classes of problems, varying in number of jobs (n) and number of machines (m) was used to perform the computational experiments. Results show that the algorithm can deal with most of the problems with less than 20 jobs in less than one hour. Thus, the method proposed in this work can solve the scheduling of many applications in manufacturing environments with limited buffers and separated setup times.

Efficient business organizations must balance quality, cost, and time constraints in competitive environments. Reflecting the complexity of this task, we consider manufacturing systems including several stages of production chains requiring time measurement. When production scheduling is not prioritized in such enterprises, several negative effects may occur. A corporation may suffer financial penalties as well as negative brand exposure, and thus may find its credibility challenged. Therefore, in this study, we propose constructive methods to minimize a total tardiness criterion, considering preventative maintenance constraints to reflect the reality of industrial practice, focusing on a no-wait flowshop environment in which jobs are successively processed without operational interruptions. In addition to proposing constructive methods to solve the no-wait flowshop production scheduling problem, a metaheuristic is presented as an approach to improve results obtained by constructive methods. Computational experiments were designed and performed to compare several production scheduling algorithms. Among various constructive heuristics considered, an algorithm called HENLL using an insertion logic showed the best performance. The proposed metaheuristic is based on the iterated greedy (IG) search method, and the results obtained demonstrated significant improvement compared to the heuristics alone. It is expected that this study may be used by production planning and control (PPC) professionals to apply the proposed method to schedule production more efficiently. We show that the proposed method successfully presented a better solution in relation to total tardiness, considering the above mentioned environment.

In this paper, the flow shop with blocking and sequence and machine dependent setup time problem aiming to minimize the makespan is studied. Two mixed-integer programming models are proposed (TNZBS1 and TNZBS2) and two other mixed-integer programming models, originally proposed for the no setup problem, are adapted to the problem. Furthermore, an Iterated Greedy algorithm is proposed for the problem. The permutation flow shop with blocking and sequence and machine dependent setup time is an underexplored problem and the authors did not find the use of mixed-integer programming models for the problem in any other work. To compare the models, a database of 80 problems was generated, which vary in number of machines and jobs. For the small sized problems, the adapted MILP model obtained the best results. However, for bigger problems, both proposed MILP models obtained significantly better results compared to the adapted models, proving the efficiency of the new models. When comparing the Iterated Greedy algorithm with the MILP models, the former outperformed the latter.

This paper addresses the minimization of makespan for the permutation flow shop scheduling problem with blocking and sequence and machine dependent setup times, a problem not yet studied in previous studies. The 14 best known heuristics for the permutation flow shop problem with blocking and no setup times are pre-sented and then adapted to the problem in two different ways; resulting in 28 different heuristics. The heuristics are then compared using the Taillard database. As there is no other work that addresses the problem with blocking and sequence and ma-chine dependent setup times, a database for the setup times was created. The setup time value was uniformly distributed between 1% and 10%, 50%, 100% and 125% of the processing time value. Computational tests are then presented for each of the 28 heuristics, comparing the mean relative deviation of the makespan, the computational time and the percentage of successes of each method. Results show that the heuristics were capable of providing interesting results.

The development and assessment of 48 heuristics for the sequence-independent setup time permutation flow shop problem (PFSP-SIST) are presented in this article. This contribution combines four tie-breaking solutions with twelve priority rules for the NEH heuristic fourth and first stage, respectively. Heuristics are evaluated on Ruiz and Allahverdi (2007) benchmark problem instances, that covers small, medium and large-size problems. The popular accelerations of Taillard were used in all tests, which were adapted to the sequence-independent setup time constraint. The aim is to reduce the longest job completion time, which is also referred to as makespan. Computation results show that using different tie-breaking strategies has a greater impact on performance than using different priority rules. The heuristics that presented the best results in relatively low computation time are those that use the FFs tie-breaking strategy procedure to the sequence-independent setup time problem.

Advanced production systems usually are complex in nature and aim to deal with multiple performance measures simultaneously. Therefore, in most cases, the consideration of a single objective function is not sufficient to properly solve scheduling problems. This paper investigates the multi-objective mixed no-idle flowshop scheduling problem. The addressed optimization case is minimizing makespan subject to an upper bound on total completion time. To solve this problem, we proposed a two-stage iterated greedy and a multi-objective constructive heuristic. Moreover, we developed a new multi-objective improvement procedure focusing on increasing the performance of the developed methods in solving the addressed problem. and a new initialization procedure. We performed several computational tests in order to compare our developed methods with the main algorithms from similar scheduling problems in the literature. It was revealed that the proposed approaches give the best results compared with other state-of-the-art performing methods.

This paper aims at presenting an algorithm for solving the blocking flow shop problem with sequence dependent setup times (BFSP-SDST) with minimization of the makespan. In order to do so, we propose an adapted Bounded Dynamic Programming (BDP-SN) algorithm as solution method, since the problem itself does not present a significant number of sources in the state-of-art references and also because Dynamic Programming and its variants have been resurfacing in the flowshop literature. Therefore, we apply the modified method to two sets of problems and compare the results computationally and statistically for instances with a MILP and a B&B method for at most 20 jobs and 20 machines. The results show that BDP-SN is promising and outperforms both MILP and B&B within the established time limit. In addition, some suggestions are made in order to improve the method and employ it in parallel research regarding other branches of machine scheduling.

This study contributes to the hybrid flow shop due to a lack of consideration of characteristics existing in real-world problems. Prior studies are neglecting identical machines, explicit and sequence-dependent setup times, and machine blocking. We propose a hybrid genetic algorithm to solve the problem. Furthermore, we also propose a mixed-integer linear programming formulation. We note a predominance of the mathematical model for small instances, with five jobs and three machines because of how fast there is convergence. The objective function adopted is to minimize the makespan, and relative deviation is used as a performance criterion. Our proposal incorporates two metaheuristics in this process: a genetic algorithm to generate sequences (the flow shop subproblem) and a GRASP to allocate the jobs in the machines (the parallel machines subproblem). The extensive computational experience carried out shows that the proposed hybrid genetic algorithm is a promising procedure to solve large-sized instances.

The integration between production and distribution to minimize total elapsed time is an important issue for industries that produce products with a short lifespan. However, the literature focus on production environments with a single stage. This paper enhances the complexity of the production system of an integrated production and distribution system by considering flowshop environment decisions integrated with a vehicle routing problem decision. In this case, each order is produced in a permutation flowshop subsystem and then shipped to its destination by a capacitated vehicle, and the objective is to sequence these orders to minimize the makespan of the schedule. This paper uses two approaches to address this integrated problem: a mixed-integer formulation and an Iterated Greedy algorithm. The experimentation shows that the Iterated Greedy algorithm yields results with a 0.02% deviation from the optimal for problems with five jobs, and is a viable option to be used in practical cases due to its short computational time.

In this paper, we address the problem of scheduling jobs in a no-wait flowshop problem with sequence-dependent setup times with the objective of minimizing makespan. This problem is well-known for being nondeterministic polynomial-time hard, and small contribution to the problem has been made. We propose a new constructive heuristic named GAPH based on a structural property. The effectiveness of the structural property is crucial given that it is responsible for 100% of the success rate of the total problems tested. The computational results demonstrate that the proposed approach is superior than three of the best-know methods in the literature such as the twos by Bianco, Dell’Olmo and Giordani (INFOR Journal: 37 (1), 3-19, 1999) and TRIPS heuristic adapted for sequence-dependent setup times objective by Brown, Mcgarvey and Ventura (Journal of the Operational Research Society, 55 (6), 614-621, 2004) in terms of the solution quality and that it requires less computational effort.