This thesis considers a single machine scheduling problem where each job produces not only its own main product but also a common type of by-product. Two different cases are investicated in consideration with distint time mechanisms of producing the common by-product. One of them is concerned with the situation where each job produces the by-product at job completion time, and the other one is concerned with the situation where each job produces the by-product continuously during processing of that job. Two performance measures are considered including weighted tardiness and weighted flow time. Both cases are shown to be NP-complete, and some dominance solution properties are characterized and used to derive a heuristic solution algorithm. The algorithm is tested for its effectiveness with several numerical problems.
본 논문은 주 작업(main-job)들이 단순공정시 같은 종류의 부산물을 생산하고, 그 부산물(by-product)들이 새로운 작업을 형성하는 경우에 대하여 연구하였다. 부산물이 각 주 작업들의 완료시간에 모두 생산되는 경우와 각 주 작업 공정중에 일정한 비율의 량이 연속적으로 생산되는 경우에 대해 모든 작업들의 가중지연시간(weighted tardiness)들의 합을 최소화 하는 경우와 가중흐름시간(weighted flow time)들의 합을 최소화하는 경우에 대해서 연구를 수행하였다. 모든 경우가 NP-complete임이 보여졌고 해법으로 우월성질(dominant solution property)들을 이용한 발견적 해법을 제시하였다. 그리고, 부산물이 일정한 비율에 따라 연속적으로 생산되고, 가중흐름시간들의 합을 최소화하는 경우에 대해서는 분지한계(branch-and-bound)기법도 제시하였다.
