(A) single machine scheduling problem with a by-product

Abstract

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.