Design And Analysis Of Approximate Algorithms For Supply Chain Scheduling With Arbitrary-size Jobs

We always face such a class of problems in food processing,ceramic calcinations and electroplate industry in the actual production process: the processing process is batch production process,the jobs have arbitrary sizes and processing time.The goal is to find a schedule of production,inventory and distribution to make the service span minimum.This class of problem is called arbitrary-size batch scheduling.We consider the problem from the overall situation,so that we can provide a comprehensive and specific schedule to make decision.This class of problem has high complexity,and have high requirement for modeling and algorithm design.In this paper,we study a class of typical batch scheduling problems,which jobs have arbitrary sizes and processing time.We consider the problems from the decision of manufactures,optimize the supply chine scheduling with processing inventory and distribution.We first consider the easy problem,which the supply chain has two links.Then we study the difficult one,which the supply chain has three links.The goal of the study is to find a schedule of the jobs and a delivery plan so that the service span and the joint cost is minimized.To solve the optimal service span problem,we consider three different cases,respectively.We give each case an approximation algorithm and the definitions of absolute worst-case ratio.We also give two examples to illustrate the two difficult cases;to solve the optimal joint cost problem,we first present an integer programming model of the problem and show that the problem under investigation is NP-hard in the strong sense.Then we provide a polynomial time algorithm.We analyze the time complexity and performance guarantee of the proposed algorithm.We consider the problem from the overall situation,so that we can provide a comprehensive and specific schedule to make decision.