Algorithm Research For Some Supply Chain Scheduling Problems On A Single Machine With Unavailability Constraints

In this thesis, we investigate the supply chain scheduling problems on a single ma-chine with unavailability constraints, which integrate job production with batch delivery. The objective function of problems is the sum of total delivery time and total delivery cost. Our study is explored from the situations with one customer, determinate process-ing time of jobs, unlimited capacity of vehicle, only one unavailable time interval on the machine to the situations with several fixed customers, processing time related to the beginning time of processing, limited capacity of vehicle and several maintenances on the machine etc.Five parts constitute this paper. In Chapter one, we first described some basic definitions and concepts of scheduling problems. Then we give a review of supply chain scheduling problem. At last, we review the research development on the scheduling problems with unavailability constraints.In Chapter two, we focus on an integrated scheduling of production and delivery in which the number of vehicles and the load capacity of each vehicle are unrestricted. Be-cause of the availability constraint of the machine, jobs in processing may be interrupted. When the machine becomes available again, the job interrupted can resume or restart processing. The completed jobs are delivered in batches to one customer by vehicles. If the interrupted job is resumable, i.e., the interrupted job can be resumed processing, we provide an optimal algorithm with polynomial time O(n2). If the interrupted job is non-resumable, i.e., the interrupted job must be restarted processing, we propose a 3/2-approximation algorithm. Moreover, we show that the problem has a polynomial time approximation scheme (PTAS).In Chapter three, we consider some supply chain scheduling problems with several fixed customers and sufficient available vehicles with capacity constraint. There are two different delivery manners. We call it the direct delivery if the completed jobs of a customer are needed to de delivered in batches from the factory; we call it the delivery with routing if a batch of completed jobs belonging to some customers is delivered with routing to these customers respectively. In the resumable scenario of interrupted job, basing on the optimal production schedules, we design two dynamic programming algorithms to find the optimal delivery schedules in two different cases of batch delivery, respectively. In the non-resumable scenario of interrupted job, we develop a 2^-approximation algorithm if completed jobs are delivered directly, where μ= min{c,1+(1 -1/c)Σλi/λmin}) c is the capacity of each vehicle and λmin is the minimum delivery cost. We obtain a 2-approximation algorithm based on the optimal schedule of the resumable situation if completed jobs are delivered with routing.In Chapter four, we mainly research a supply chain scheduling problem with deteri-orating jobs. The actual processing time depends on the deteriorating operator and the beginning time of processing. The interrupted job is non-resumable. And the completed jobs before the unavailability interval must be delivered before or by the start time of the unavailability interval. We show that the problem is NP-hard, and present a pseudo-polynomial-time dynamic programming algorithm after studying the properties of the optimal schedule. Moreover, we obtain the lower bound and the upper bound of the ob-jective function value of the problem and achieve a full polynomial time approximation scheme (FPTAS).In Chapter five, a supply chain scheduling problem with periodic unavailability in-tervals are studied. The problem is raised from the logistics management of medical materials in the warehouse of a hospital. Medical materials are wrapped into packages by a baler and the wrapped packages are dispatched to the departments often before workers are off duty or before the baler is maintained. The wrapping procedure is not always allowed to be interrupted in the hospital because the interruption can make some medical materials to be antihygienic. The delivery is required a payment from the ware-house. The manager of the warehouse wants to efficiently utilize the wrapping machine and reduce the times of distributions to decrease logistics cost. If we regard the baler as a single machine and medical materials as jobs, the problem can be summarized as a supply chain scheduling problem with one machine. If the unavailability intervals are periodic, processing of any job is non-resumable and the completed jobs are delivered by one vehicle without capacity constraint to customers just before each maintenance, we show that the problem is strongly NP-hard and provide a 2-approximation algorithm. Moreover, a branch-and-bound algorithm is obtained to find the optimal schedule of the problem. From the numerical simulation results, the approximation algorithm is shown to be efficient. If the length of each availability interval is limited by a constant and the delivery time is not restricted, we obtain the optimal schedule for resumable case in poly-nomial time, and present a 2-approximation algorithm for non-resumable case because the latter problem is shown to be a NP-hard problem in the strong sense.