Abstract
This PhD dissertation proposes novel optimization methods for solving numerous variants of the Flexible Job Shop Scheduling Problem (FJSSP). The FJSSP is an NP-hard optimization problem introduced by Brucker and Schlie (1990). The basic formulation of the FJSSP, is a generic, extensible and has been used to model a plethora of operational realities and realistic production processes that appear in various manufacturing environments (Li and Gao 2020). In addition, due to its difficulty, the FJSSP has been the main focus of multiple research efforts that aim to develop efficient algorithms (meta-heuristics) for producing high quality solutions in short computational times. The classical FJSSP is defined as follows: There is a set of jobs where each job consists of one or more operations/activities. Every operation can be processed by one or more machines with different processing times. Every operation may have at most one successor or predecessor operations that also belong to the same ...
This PhD dissertation proposes novel optimization methods for solving numerous variants of the Flexible Job Shop Scheduling Problem (FJSSP). The FJSSP is an NP-hard optimization problem introduced by Brucker and Schlie (1990). The basic formulation of the FJSSP, is a generic, extensible and has been used to model a plethora of operational realities and realistic production processes that appear in various manufacturing environments (Li and Gao 2020). In addition, due to its difficulty, the FJSSP has been the main focus of multiple research efforts that aim to develop efficient algorithms (meta-heuristics) for producing high quality solutions in short computational times. The classical FJSSP is defined as follows: There is a set of jobs where each job consists of one or more operations/activities. Every operation can be processed by one or more machines with different processing times. Every operation may have at most one successor or predecessor operations that also belong to the same job. Also, every machine can execute only one operation at a time and no pre-emption is allowed. The goal is to minimize the makespan, i.e. the completion time of the latest operation. One of the FJSSP variants that this thesis focuses on is the FJSSP with arbitrary precedence graphs. This variant aims to generalize the FJSSP by considering arbitrary precedence graphs that are used to describe the precedence relationships between the operations of a job. For this problem, mixed integer as well as constraint programming (CP) models are presented. In addition, a novel evolutionary algorithm (EA) is proposed to solve the problem. This framework adopts a path relinking mechanism that is able to recombine more than two solutions during the evolution of the population. Search intensification is performed using a tabu search algorithm, that is equipped with efficient feasibility and makespan estimation methods. The latter, uses new heorems that extend previous theoretical results of the FJSSP literature Dauzere-Peres and Paulli (1997). Detailed computational experiments on well-known benchmark sets of the literature show that the EA outperforms the current state-of-the-art by producing 59 new best solutions for a total of 228 problem instances, while 61 improved lower bounds are reported. To further explore the impact of arbitrary precedence graphs on the quality of the generated production schedules, a thorough experimentation is performed on new small and large scale problem instances. The goal is to study the effect of the problem flexibility and the precedence graph density on the makespan but also the difficulty of producing good upper bounds. Next, in an effort to fill the gaps of the literature regarding problems with combinations of different resource types, the FJSSP with multiple resource constraints is studied. This problem includes renewable, non-renewable and cumulative resources in the form of tools, utilities, limited capacity buffers, WIP buffers as well as arbitrary material resources. To solve the problem, a CP-based evolutionary algorithm is proposed. This framework uses long-term memory structures to store information about single operation-to-machine assignments and operation pair-to-machine assignments encountered in high quality and diverse solutions during the search process. The proposed constraint extraction operators use this information to generate constraint expressions which are imposed to the CP solver in an effort to guide the search to promising regions of the solution space. A comprehensive experimental study on well-known benchmark sets of the literature showcases the efficiency and the high competence of the framework compared to the state-of-the-art. To that end, 34 new best solutions are reported for well-known benchmark sets of the FJSSP, the Blocking Job Shop Scheduling Problem (BJSSP) and the Unrelated Parallel Machine Scheduling with Resources (UPMR) literature. To study the effect of the different resource types on the makespan, detailed computational experiments have been performed on new small and large-scale problem instances. Another subject of this thesis is the integration of optimization methods in manufacturing systems. At first, the integration of an optimization service within a Cognitive Digital Twin (CDT) framework is presented. The optimization service is developed so as to provide solutions for the production scheduling problem of an automotive manufacturing facility. The optimization problem can be modeled as an FJSSP with renewable and cumulative resources that also considers scheduled and unscheduled maintenance activities. The goal is to minimize the effect of line or machine breakdown events on the delivery of the production orders by carefully scheduling maintenance activities. A CP model is proposed to solve the problem, while the design and the integration of the optimization module within the CDT framework is presented. To evaluate the performance and the effectiveness of the proposed solution method real and randomly generated data are used. A thorough experimental study is performed in an effort to measure the impact of maintenance activities and resource constraints to various production schedule metrics such as, the makespan, the total flow time and the total workstation idle time. Lastly, a Situation Aware Manufacturing System (SAMS) is presented. The SAMS aims to identify and react to disruption events that may occur in manufacturing environments by coupling Industry 4.0 technologies such as predictive analytics, simulation and optimization. The SAMS framework adopts a design science research (DSR) approach in an effort to enable the identification and handling of disruptive events, the enumeration of user requirements as well as the validation of its effectiveness in a practical level. Two instantiations of SAMS are presented that correspond to two real-life manufacturing environments from the electronics and the automotive manufacturing industries, respectively. A comprehensive experimental study showcases the efficiency and effectiveness of the proposed framework in both applications.
show more
