Graph decomposition heuristic for machine scheduling problems

다국어 초록 (Multilingual Abstract)

A graph decomposition technique has been used for the application of machine scheduling problems. The method divides a problem with a series of sub-problem by solving partitioning problems. These sub-problems are turned out to be mutually exclusive and exhaustive assignment problems. The decomposition methodology makes only a part of the scheduling decisions at first while leaving the rest of the decisions to be made dynamically. This method retains flexibility in the schedule which can be used to improve its robustness. The proposed method can indeed handle scheduling disturbances more effectively when compared with traditional methods.

목차 (Table of Contents)

• 1. Introduction
• 2. Problem Statement
• 3. Problem Analysis
• 3.1 Lower Bounds
• 3.2 Upper Bounds
• 4. Solution Methodology
• 4.1 The Price Directed Heuristic(PDH)
• 4.2 The Index Based Heuristic(IBH)
• 5. Experimental Results
• 5.1 Robustness of the Partial Schedule
• 6. Conclusions
• References