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.

This paper presents a two-stage hybrid flow shop scheduling problem with setup and assembly operations. The proposed study of this paper considers one kind of product with a quantity of demand where each product is made by assembling a set of different parts. At first, the parts are manufactured in a two-stage hybrid flow-shop and then the parts are assembled into products on assembly stage. Setup operations are needed when a machine starts processing the parts or it changes items. The considered objective is minimizing the completion time of all products. Since the problem is classified as NP-hard class, a combinatorial algorithm is proposed. The proposed algorithm is a three-step procedure where we use heuristic, genetic algorithm (GA), simulated annealing (SA), NEH and Johnson’s algorithm. Three lower bounds are presented and improved to evaluate the proposed algorithms. An extensive computational experiment is conducted to compare the performances of the proposed algorithms.