Research On Algorithms Of Some Supply Chain Scheduling Problems

Supply chain scheduling focuses on the coordinated models, complexity and algorithms with respect to production, batching and delivery. In this paper we study supply chain scheduling problems in which the number and capacity of vehicles are bounded or unbounded on single machine and parallel machines.For the environment of single machine, we consider two problems. For the first problem, there is sufficient numbers of vehicles available and each vehicle is uncapacitated. Jobs have release dates and preemption is allowed. The objective is to minimize the maximum delivery lateness and the total delivery cost. We propose an efficient optimal algorithm with the complexity of O(n3). For the second problem, there is a limited numbers of vehicles and each vehicle has a capacity limit. The machine has to be stopped for maintenance after continuously working for a period of time. And suppose that the longest possible continuously working time for the machine is T and it should take t time units for maintenance. We investigate the problem with the objective of minimizing the time at which the vehicle finishes delivering the last batch and returns to the manufacturing center. We provide a heuristic algorithm with worst-case approximation ratio of2.For the environment of parallel machines, we consider three problems in which there is sufficient numbers of vehicles available and each vehicle is uncapacitated. For the first two problems, the objective is to minimize the maximum delivery lateness and the total delivery cost. For the case of single customer, we study the problem of jobs with release dates and give a heuristic algorithm. We show that it is asymptotically optimal as the number of jobs goes infinity. For the case of multiple customers, we present a heuristic algorithm and analyze the asymptotic performance. For the third problem, we investigate the problem of multiple customers and the objective of it is to minimize the sum of the total delivery time and the total delivery cost. Jobs have release dates. We present a heuristic algorithm with worst-case approximation ratio of3-1/...