Date of Award

August 2020

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Mechanical and Aerospace Engineering

Advisor(s)

Utpal Roy

Keywords

algorithms, graph coloring, Maximum weighted independent set, optimization, process planning, scheduling

Subject Categories

Engineering

Abstract

Process planning and scheduling (PPS) is an essential and practical topic but a very intractable problem in manufacturing systems. Many research studies use iterative methods to solve such problems; however, they cannot achieve satisfactory results in both quality and computational speed. Other studies formulate scheduling problems as a graph coloring problem (GCP) or its extensions, but these formulations are limited to certain types of scheduling problems. In this dissertation, we propose a novel approach to formulate a general type of the PPS problem with resource allocation and process planning integrated towards a typical objective, minimizing the makespan. The PPS problem is formulated into an undirected weighted conflicting graph, where nodes represent operations and their resources; edges represent constraints, and weight factors are guidelines for the node selection at each time slot. Then, the Maximum Weighted Independent Set (MWIS) problem, which considers a graph with weights assigned to nodes and seeks to discover the “heaviest” independent set, that is, a set of nodes with maximum total weight so that no two nodes in the set are connected by an edge, can be solved to find the best set of operations with their desired resources for each discrete time slot.

This proposed approach solves the PPS problem directly (a direct method in computational mathematics context). We establish that the proposed approach always returns a feasible optimum or near-optimum solution to the PPS problem.

The performance of the proposed approach for the PPS problem depends on the accuracy and computational speed of solving the MWIS problem. We propose a divide-and-conquer algorithm structure with relatively low complexity for solving the MWIS problem. An exact MWIS algorithm and an All Maximal Independent Set Listing (AMISL) algorithm are developed based on this algorithm structure. The proposed algorithm structure can also be used to compose the exact MWIS algorithm with existing approximation MWIS algorithms. This is an effective way to improve the accuracy of existing approximation MWIS algorithms or improve the computational speed of the exact MWIS algorithm.

All eight algorithms for the MWIS problem, the exact MWIS algorithm, the AMISL algorithm, two approximation algorithms from the literature, and four composed algorithms, are tested on the test instances based on the PPS application environment. The different configurations of the proposed approach for solving the PPS problem are tested on a real-world PPS example and further designated test instances to evaluate the scalability, accuracy, and robustness.

Access

Open Access

Download

Included in

Engineering Commons

Share

COinS