Batch Supply, Processing, Distribution Supply Chain Scheduling Problem

Scheduling problem which focuses on arranging jobs’ processing sequence reasonably to get optimal target value under some constraints is an important part in combinatorial optimization. Supply chain scheduling applies theories in scheduling to supply chain management to achieve an optimal objective value, which integrates material supply, jobs’ processing, and production delivery. With the development of the times and the intensification of competition, how to arrange the production and transportation to meet customers’demands become particularly important. In this paper we study a supply chain scheduling problem with batch processing, supply, and delivery considerations to minimize the makespan. Structures of this thesis are organized as follows:In the first chapter, we introduce some basic concepts, such as the 3-Partition problem and the theory of algorithm complexity, and so on. Then we give the definitions of symbols used in this article. A brief summary of this paper about the background, the research status and our results is given at last.In the second chapter, we study the supply chain scheduling problem with batch processing and delivery considerations to minimize the makespan. Either the number of manufacturer or customer is one. We define the manufacturer as a p-batch machine whose capacity is B. The transporter is a vehicle of capacity K. We have n jobs to be processed and delivered. The whole scheduling process can be divided into two stages. During stage one, jobs are processed on the batch processing machine. Jobs have finished its processing on machine can be delivered to customer in stage two when the vehicle is available. For the case K≥n, we present an optimal algorithm runs in O(n log n) time. Then we analysis the case K<n. For the subcase K = B, we present an optimal algorithm runs in O(n logn) time. For two special subcases K> B and K< B, we present approximation algorithms which have approximation ratios less than 3/2, running in O(nB3 log n) time and O(nB log n) time, respectively. Finally, for the general case we provide a approximation algorithm which has approximation ratio less than 3/2, running in O(nB3 log n) time.In the third chapter, we study a supply chain scheduling problem with supply, batch processing, and delivery considerations to minimize the makespan. On the basis of problem in chapter two we add a supplier, so we divide this problem into three stages. A vehicle of capacity K1 transports jobs from supplier’s warehouse to manufactory in the first stage. In the second stage, jobs that have been shipped to the manufactory will be processed on machine of capacity B. Jods have finished its processing on machine will be delivered to customer by a vehicle of capacity K2 in the third stage. We show that the problem is strong NP-hard, and propose a approximation algorithm runs in O(nB3 log n) time which has approximation ratio less than 5/2. We also give some optimal algorithms run in polynomial time for some special cases.