Some Scheduling Problems In The Supply Chain Management

This thesis mainly concerns a new scheduling model for a firm with an option of outsourcing and a flow shop problem with a batching machine. We first introduce basic notions of scheduling problem, approximation algorithms and competitive analysis.In Chapter 2, we investigate the outsourcing situations which based on a scheduling problem. We prove it equals to a subset sum problem, thus the problemcan be solved by a dynamic program in O(nP) time. We then develop an algorithmA_εand approximation algorithm A_l for the problem and we also prove A_εto beFPTAS.In Chapter 3, we investigate a flow shop problem with a batching machineF₂→D|B,v=1,k=1|C_max.We formulate the problem as a mixed integerprogramming model. We also show that the problem is strongly NP-hard by a reduction from 3-partition, which is known to be NP-hard in the strong sense. While the processing order is set, we develop a heuristic algorithm and prove 2 to be the worst case ratio. We also show the tightness of the upper bound of the heuristic algorithm.