This study focuses on the study of a unique but commonly occurring manufacturing problem of scheduling of customized jobs consisting of two operations on a single multi-purpose machine with the performance objective of minimizing the number of tardy jobs (jobs that are not completed by their due dates). Each customized job to be complete needs one unique operation and one common operation performed on it. We considered a static case in this work. The objective of minimizing the number of tardy jobs is considered where all jobs have equal weights and the maximum tardiness has no effect on the performance. This problem is proved in literature as NP-hard and hence practically very difficult to obtain optimal solution within reasonable computational time. Till date only a pseudo-polynomial algorithm is given to solve this problem with no concrete computational experiments designed to prove the efficiency and working of the algorithm for different problem instances.
We propose a heuristic algorithm based on the Moore-Hodgson's algorithm combining with other procedures and optimal schedule properties from the literature to solve this problem. In literature, Moore-Hodgson's algorithm is an efficient heuristic algorithm that minimizes the number of tardy jobs for the classical single machine one-operation problems.
The performance of the heuristic is evaluated through extensive computational experiments for large real size data. The obtained results are compared to the solutions obtained by implementing the optimal pseudo-polynomial algorithm and the performance of the heuristic is tested on large data sets. The test data for the computational experiments are generated randomly using MATLAB 6.1. Future directions of research and development on the problem to improve the obtained solution by the heuristic algorithm are given.
| Identifer | oai:union.ndltd.org:USF/oai:scholarcommons.usf.edu:etd-2509 |
| Date | 14 November 2003 |
| Creators | Yeleswarapu, Radhika M |
| Publisher | Scholar Commons |
| Source Sets | University of South Flordia |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Graduate Theses and Dissertations |
| Rights | default |
Page generated in 0.002 seconds