Supply Chain Scheduling On Single Machine With Deterioration

The theory of scheduling is one of the most important branches in operations research.Supply chain scheduling is a new area that integrates scheduling and batch delivery. Schedulingwith deterioration and scheduling with rejection are two new scheduling models, which attractmore and more attention recently. In this thesis we combine three scheduling theories mentionedabove and discuss three related problems. The structure of this article is as follows:The first chapter introduces some notions that we will use in this thesis. Such as what aresupply chain scheduling and scheduling with deterioration, the definition of the complexity ofalgorithms, and so on. Then the main work of this paper is briefly summarized in this chapter.In the second chapter, we study some problems of supply chain scheduling withdeterioration. Jobs belong to one customer which should be processed by a manufacturer on asingle machine. The processing time of each job is a simple linear increasing function of itsstarting time. After being processed, the jobs should be delivered to the customer by vehicles.The completion time of each job is the time when it arrives at the customer. The jobs deliveredtogether in the same vehicle called a batch. The capacity of each batch is z n.In each batch, adistribution cost should be paid. The first objective is to minimize the sum of total completiontime and distribution cost. And the second is to minimize the sum of maximum lateness anddistribution cost. We provide polynomial time algorithms for these problems respectively.In the third chapter, based on the first problem of the second chapter, we consider the caseof job rejection. For each job, the manufacturer can either receive it or reject it. If the job isrejected, then the rejection penalty has to be paid. If it is accepted, then the processing time ofthe job is a simple linear increasing function of its starting time. After being processed, theaccepted jobs should be delivered to the customer by some vehicles. The completion time ofeach job is the time when it arrives at the customer. The jobs delivered together in the samevehicle called a batch. In each batch, a distribution cost should be paid. The objective is tominimize distribution cost, total completion time of the accepted jobs and total penalty of therejected jobs. For this problem, we provide a dynamic programming algorithm, which runs inpolynomial time.