Mathematical modeling and two efficient branch and bound algorithms for job shop scheduling problem followed by an assembly stage
ISSN: 0368-492X
Article publication date: 22 January 2021
Issue publication date: 15 November 2021
Abstract
Purpose
Two-stage production systems including a processing shop and an assembly stage are widely used in various manufacturing industries. These two stages are usually studied independently which may not lead to ideal results. This paper aims to deal with a two-stage production system including a job shop and an assembly stage.
Design/methodology/approach
Some exact methods are proposed based on branch and bound (B&B) approach to minimize the total completion time of products. As B&B approaches are usually time-consuming, three efficient lower bounds are developed for the problem and variable neighborhood search is used to provide proper upper bound of the solution in each branch. In addition, to create branches and search new nodes, two strategies are applied including the best-first search and the depth-first search (DFS). Another feature of the proposed algorithms is that the search space is reduced by releasing the precedence constraint. In this case, the problem becomes equivalent to a parallel machine scheduling problem, and the redundant branches that do not consider the precedence constraint are removed. Therefore, the number of nodes and computational time are significantly reduced without eliminating the optimal solution.
Findings
Some numerical examples are used to evaluate the performance of the proposed methods. Comparison result to mathematical model (mixed-integer linear programming) validates the performance accuracy and efficiency of the proposed methods. In addition, computational results indicate the superiority of the DFS strategy with regard to CPU time.
Originality/value
Studies about the scheduling problems for two-stage production systems including job shop followed by an assembly stage traditionally present approximate method and metaheuristic algorithms to solve the problem. This is the first study that introduces exact methods based on (B&B) approach.
Keywords
Citation
Daneshamooz, F., Fattahi, P. and Hosseini, S.M.H. (2021), "Mathematical modeling and two efficient branch and bound algorithms for job shop scheduling problem followed by an assembly stage", Kybernetes, Vol. 50 No. 12, pp. 3222-3245. https://doi.org/10.1108/K-08-2020-0521
Publisher
:Emerald Publishing Limited
Copyright © 2020, Emerald Publishing Limited