Flexible Job Shop Scheduling Problems with Arbitrary Precedence Graphs

Gregory A. Kasapidis, Dimitris C. Paraskevopoulos, Panagiotis P. Repoussis and Christos D. Tarantilis

Production and Operations Management, 2021, vol. 30, issue 11, 4044-4068

Abstract: A common assumption in the shop scheduling literature is that the processing order of the operations of each job is sequential; however, in practice, there can be multiple connections and finish‐to‐start dependencies among the operations of each job. This paper studies flexible job shop scheduling problems with arbitrary precedence graphs. Rigorous mixed integer and constraint programming models are presented, as well as an evolutionary algorithm is proposed to solve large‐scale problems. The proposed heuristic solution framework is equipped with efficient evolution and local search mechanisms as well as new feasibility detection and makespan estimation methods. To that end, new theorems are derived that extend previous theoretical contributions of the literature. Computational experiments on existing benchmark datasets show that the proposed solution methods outperform the current state‐of‐the‐art. Overall, 59 new best solutions and 61 new lower bounds are produced for a total of 228 benchmark problem instances of the literature. To explore the impact of the arbitrary precedence graphs, lower bounds and heuristic solutions are generated for new large‐scale problems. These experiments illustrate that the machine assignment flexibility and density of the precedence graphs, affect not only the makespan, but also the difficulty of producing good upper bounds.

Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1111/poms.13501

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:popmgt:v:30:y:2021:i:11:p:4044-4068

Ordering information: This journal article can be ordered from
http://onlinelibrary ... 1111/(ISSN)1937-5956

Access Statistics for this article

Production and Operations Management is currently edited by Kalyan Singhal

More articles in Production and Operations Management from Production and Operations Management Society
Bibliographic data for series maintained by Wiley Content Delivery ().