Optimization Online


Flexible Job Shop Scheduling Problems with Complex Precedence Graphs

Gregory A. Kasapidis(gkasapidis***at***aueb.gr)
Dimitris C. Paraskevopoulos(dimi***at***city.ac.uk)
Panagiotis P. Repoussis(prepousi***at***aueb.gr)
Christos D. Tarantilis(tarantil***at***aueb.gr)

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 complex precedence graphs. At first, rigorous mixed in- teger and constraint programming models are presented that adequately capture all problem features. Furthermore, an evolutionary algorithm is proposed to generate heuristic solutions. The proposed algorithmic framework is equipped with novel learning and local search mecha- nisms as well as new feasibility detection and makespan estimation methods. Computational experiments on existing benchmark data sets show that the new solution method outper- forms all state-of-the-art heuristics, while 12 new best solutions are produced for a total of 48 instances. To explore the impact of the multiple precedence constraints, lower and upper bounds are generated considering new medium- and large-scale problem instances. These ex- periments illustrate that the problem becomes significantly harder to solve when precedence constraints are added; however, depending on the machine assignment flexibility and density of the precedence graphs the magnitude of this effect may vary.

Keywords: Parallel Machine Scheduling, Flexible Job Shop Scheduling, Mathematical Programming, Constraint Programming, Evolutionary Algorithms

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Applications -- OR and Management Sciences (Scheduling )

Citation: Department of Management Science and Technology, Athens University of Economics and Business, 08/2019

Download: [PDF]

Entry Submitted: 10/30/2019
Entry Accepted: 10/30/2019
Entry Last Modified: 10/30/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society