City Research Online

Flexible job shop scheduling problems with arbitrary precedence graphs

Kasapidis, G. A., Paraskevopoulos, D. C. ORCID: 0000-0002-7004-3263, Repoussis, P. P. and Tarantilis, C. D. (2021). Flexible job shop scheduling problems with arbitrary precedence graphs. Production and Operations Management, doi: 10.1111/poms.13501

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 exible 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 effcient 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 data sets 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.

Publication Type: Article
Additional Information: This is the peer reviewed version of the following article: Kasapidis, G.A., Paraskevopoulos, D.C., et al. Flexible job shop scheduling problems with arbitrary precedence graphs. Prod Oper Manag. (2021), which has been published in final form at https://doi.org/10.1111/poms.13501. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions.
Publisher Keywords: Constraint Programming, Evolutionary Algorithms, Flexible Job Shop Scheduling, Mathematical Programming
Subjects: H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management
Departments: Business School > Management
Date available in CRO: 21 Jun 2021 09:22
Date deposited: 21 June 2021
Date of acceptance: 1 May 2021
Date of first online publication: 18 June 2021
URI: https://openaccess.city.ac.uk/id/eprint/26312
[img] Text (Article) - Accepted Version
This document is not freely accessible until 18 June 2023 due to copyright restrictions.

To request a copy, please use the button below.

Request a copy
[img] Text (Appendices) - Accepted Version
This document is not freely accessible until 18 June 2023 due to copyright restrictions.

To request a copy, please use the button below.

Request a copy

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login