Study On Scheduling Problems In Supply Chain Management

Scheduling problem, one of the classical combinatorial optimization problems, has gained great attention from both manufacturers and academic researchers. This thesis mainly concerns some scheduling problems in supply chain management. As we all know, supply chain is composed of several steps, thus the integrated investigation of scheduling and other steps of supply chain is necessary. We considered some scheduling problems with transportation. The thesis is split into four chapters.We first introduce some related preliminary concepts of supply chain and scheduling and then summarize recent research results of scheduling problems with transportation in chapter 1.In chapter 2, we investigate scheduling problems with transportation, in which every job needs to be delivered to its customer after production and the completion time is defined as the time when the job arrives at its customer. There is one vehicle with limited capacity, and each job occupies different size in the vehicle during transportation. The goal is to minimize the maximum job completion time. When there is a single machine for processing jobs and only one customer, we present a asymptotical best possible polynomial-time approximation algorithm with worst case ratio of 3/2 + (?) ((?)→0). When there are two parallel machines for processing jobs and only one customer, we propose a polynomial-time approximation algorithm with worst case ratio of 5/3.In chapter 3, we consider scheduling problems with raw material and completed product delivery between two different processing centers. Each processing center is allowed to process jobs belonging to the other one, and in doing this, transportation cost occurs. If a processing center processes jobs belonging to the other one, according to different characteristics of the processing centers and jobs, three cases are studied: (1) Before processing, raw material do not need to be transported to the other machine and after processing, the completed jobs must be transported back to the original machine. (2) Before processing, raw material must be transported to the other machine and after processing, the completed jobs do not need to be transported back to the original machine. (3) Before processing, raw material must be transported to the other machine and after processing, the completed jobs must be transported back to the original ma- chine. The goal is to minimize the maximum job completion time. For the above three problems, we present linear time approximation algorithms with worst case ratio of 4/3, 4/3, and 3/2, respectively. Besides, an dynamic programming algorithm is given for each problem.In chapter 4, we study an integrated production and distribution scheduling problem with committed delivery dates. In this problem, the manufacturing company uses a third-party logistics service provider for shipping the completed order with different committed delivery dates to customers. The shipping cost of an order is relative to the order size and the delivery time requested. The goal is to determine a production schedule for accepted orders and a shipping time for delivering each completed order so that the total shipping cost is minimum subject to the constraint that all the orders are completed and delivered to their customers on or before the respective committed delivery dates. For this strongly NP-hard problem, we propose a polynomial-time heuristic algorithm and show that the worst-case performance ratio is bound by 2 and this bound is tight.