A branch-and-cut approach for the distributed no-wait flowshop scheduling problem


Avci M., AVCI M. G., Hamzadayı A.

COMPUTERS & OPERATIONS RESEARCH, vol.148, 2022 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 148
  • Publication Date: 2022
  • Doi Number: 10.1016/j.cor.2022.106009
  • Journal Name: COMPUTERS & OPERATIONS RESEARCH
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, PASCAL, ABI/INFORM, Aerospace Database, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Communication Abstracts, Computer & Applied Sciences, INSPEC, Metadex, zbMATH, Civil Engineering Abstracts
  • Keywords: Scheduling, Flowshop scheduling, Distributed no-wait, Branch-and-cut, SEARCH ALGORITHM, OPTIMIZATION ALGORITHM, MAKESPAN, FORMULATIONS
  • Van Yüzüncü Yıl University Affiliated: Yes

Abstract

The distributed no-wait flowshop scheduling problem (DNWFSP) is an extension of the permutation flowshop scheduling problem with multiple factories and no-wait constraints. The DNWFSP consists of two decisions, namely, assigning jobs to the factories and sequencing the set of jobs assigned to the same factory. The no -wait constraints require that jobs have to be processed without any interruption between operations. Since the introduction of the DNWFSP, a number of metaheuristic approaches were developed to solve it. However, there exists no exact solution approach for the DNWFSP to the best of our knowledge. In this regard, a branch -and-cut (BC) algorithm is proposed to solve the DNWFSP. The proposed BC is integrated with a heuristic algorithm to obtain good upper bounds. Moreover, a set of symmetry breaking constraints are employed in the models to strengthen the formulations. The performance of BC is evaluated on a set of benchmark problem instances available in the related literature. The proposed BC is numerically compared with mixed-integer programming formulations of the DNWFSP which are solved by a commercial solver. The results obtained from the computational experiments reveal the effectiveness of the proposed approach. The proposed BC is able to solve all small-size instances, as well as, 206 out of 660 large-size instances to optimality. Besides, it is worth to mention that the average percentage gap for the large-size instances with two factories is only 0.43%.