Algorithms for minimizing the number of tardy jobs for reducing production cost with uncertain processing times

摘要

This paper addresses a manufacturing system consisting of a single machine. The problem is to minimize the number of tardy jobs where processing times are uncertain, which are within some intervals. Minimizing the number of tardy jobs is important as on-time shipments are vital for lowering cost and increasing customers' satisfaction for almost all manufacturing systems. The problem is addressed for such environments where the only known information is the lower and upper bounds for processing times of each job since the exact processing times may not be known until all jobs are processed. Therefore, the objective is to provide a solution that will perform well for any combination of feasible realizations of processing times. First, a dominance relation is established. Next, several versions of an algorithm, incorporating the dominance relation, are proposed. The computational analyses reveal that the error of one of the versions of the algorithm is at least 60% smaller than the errors of the other versions of the algorithm. Besides, the performance of this version is very close to the optimal solution, i.e., on average, 1.34% of the optimal solution.