This thesis proposes a new but intuitive algorithm for determining an optimal solution to two stage production sequencing problem with following characteristics. There are jobs to be sequenced in two stage production environment; each production stage is equipped with a single facility; jobs to be sequenced are subject to due date constraints; facilities in both stages require setup prior to processing each job; setup times in both stages are sequence dependent, and setup cost is assumed to be directly proportional to setup time; and the optimal solution is one that minimizes the total setup cost without violating job-due dates.
This new algorithm employs the revised selection method which reduces the number of comparisons among the feasible solutions in the process of obtaining the optimal solution by using the notions of pseudo due date and latest start date. The rather complicated algorithm developed by Uskup and Smith is introduced for comparison, which employs controlled enumeration through branch-and-bound procedure, with feasiblity test.
It is shown that, for many practical production scheduling situations with several number of jobs(less than 7), the revised selection method reduces computer (CPU) time about 10% compared with the method by Uskup and smith.