Back to search

University of South Florida

Scheduling Of 2-Operation Jobs On A Single Machine To Minimize The Number Of Tardy Jobs

Abstract

dc:description

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.

Degree

thesis:*
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Industrial Engineering
Grantor
University of South Florida
Year dc:date
2003

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Yeleswarapu, Radhika M
Contributors dc:contributor
  • Michael X. Weng, Ph.D.
  • Tapas K. Das, Ph.D.
  • Grisselle Centeno, Ph.D.

Subjects

dc:subject × 7

Rights

Language dc:language
EN-US

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/1510

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Yeleswarapu, Radhika M. Scheduling Of 2-Operation Jobs On A Single Machine To Minimize The Number Of Tardy Jobs. Thesis thesis, University of South Florida, 2003. https://digitalcommons.usf.edu/etd/1510