National Technical University of Athens (NTUA)
Συστήματα αλγορίθμων λεπτομερειακού χρονικού προγραμματισμού παραγωγής
Abstract
dc:descriptionThe aim of this thesis is to provide a thorough assessment regarding the application of the complex and multifaceted hybrid metaheuristics designed for the deterministic job shop scheduling problem, henceforth JSSP, to real world problems. The JSSP problem has been a topic of active research for the past five decades attracting numerous researchers from the fields of operations research, production management and combinatorial optimization. The literature review and computational study of various state of the art algorithms has eloquently evinced that no single strategy can effectively tame this stubborn and intractable problem. Therefore, the research efforts have focused on hybrids that combine underlying myopic heuristics and general meta-techniques. The former are used to incorporate the much necessitated problem specific knowledge stemming from the morphology of the solution space, whereas the latter aim at guiding the search away from the numerous local minima that may be encountered by the algorithm. The current state of the art algorithms, abetted by the constant evolution of processing units and the augmentation of computing power, have managed to achieve high levels of robustness and effectiveness on a wide range of available benchmark problems, while remaining efficient with relatively small computational overhead. This gives rise to the research question posed within the scope of this thesis: are these types of algorithms applicable and efficient in dynamic shop floors as they are on the JSSP? A brief answer derived from the results of the empirical analysis performed is the following: they are not applicable, unless they undergo a significant degree or parameterization, to the point of altering the initial characteristics, and are combined with additional heuristic mechanisms and decision support tools. This statement is in full alignment with the architecture of the APS (Advanced Planning and Scheduling) systems whose development and implementation are geared towards the fulfillment of practical detailed scheduling requirements. The algorithms embedded within these systems are either exact or approximate and are supported by an array of decision support tools to aid the planner in the decision making process. Unfortunately, the implementation of APS systems is not without serious and sometimes insurmountable shortcomings, such as high acquisition and parameterization cost, time consuming schedule generation, redundant functionality, inability by the algorithms to assimilate the endemic particularities of a production process, steep learning curve and problematic interoperability with the rest of the IT infrastructure. Therefore, it is obvious that APS systems are a prohibitory choice for SMEs (Small to Medium Enterprises) and an alternate approach is necessitated. As it happens, this is the main contribution of this thesis: an approach for the application of efficient and effective JSSP algorithms to dynamic problem structures in the form of complete DSSs (Decision Support Systems). In order to construct this blueprint, the research process was sectored in two distinct parts. The first part focuses solely on deterministic detailed production scheduling. An analysis of the solution space properties and the theoretical background of the JSSP is conducted, followed by an extensive literature review regarding the available algorithms applied to combinatorial optimization problems. The conclusions drawn from the review are utilized in order to develop a parallel hybrid metaheuristic which combines genetic algorithms and tabu search. The hybrid is validated through its application on all the available 242 benchmark problems from the JSSP domain, as well as 40 problems from the FSSP (Flow Shop Scheduling Problem). The results clearly demonstrate that the proposed algorithm is state of the art for the FSSP and the state of the art genetic local search method for the JSSP. The second part of the thesis is dedicated to the identification of the preferred approach for adapting the proposed algorithm to dynamic detailed production scheduling problems. In this respect, it was deemed essential first and foremost to study the key differences between theory and practice and highlight the points that merit investigation. Afterwards, an elaborate literature survey is performed concerning the embedded algorithms, functionality and implementations of APS systems. The subsequent conclusions are exploited to transform the proposed algorithm into the eGantt DSS. The effectiveness, robustness and efficiency of the system are tested by its application to a real world case study from the metal forming industry and specifically the manufacturing of light metal sheet products such as door locks and aluminum window panes. The cumulative results of both the first and the second part validate the proposed approach of the thesis.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2009
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Spanos, A.
- Σπανός, Αθανάσιος
Subjects
dc:subject × 16- Λεπτομερειακός προγραμματισμός παραγωγής
- Βελτιστοποίηση
- Μεταευρετικοί αλγόριθμοι
- Ευρετικοί αλγόριθμοι
- Συστήματα υποστήριξης αποφάσεων
- Διακριτή και ροϊκή παραγωγή
- Detailed production scheduling
- Optimization
- Metaheuristics
- Heuristics
- Decision support systems
- Job shops and flow shops
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Μηχανολόγου Μηχανικού
- Engineering and Technology
- Mechanical Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/28710