The Research For The Machine Scheduling With A Maintenance Interval And Job Delivery Coordination

Scheduling problem is one of the classical combinatorial optimization problems. In recent decades, new scheduling problems with practical background get more attentions. The thesis mainly concerns the machine scheduling with a maintenance interval and job delivery coordination, in which the machine environment is a single machine with a maintenance interval. The study focuses on the approximate algorithm design and the worst-case ratio analysis. The thesis is split into ?ve chapters.In chapter 1, we ?rst introduce some related preliminary concepts of scheduling problem,and then summarize the research results of scheduling problems with job delivery or with availability constraint.In chapter 2, machine scheduling problem with job delivery and a maintenance interval coordination is investigated. In the problem, jobs of varying size are delivered by one vehicle to a customer after they are processed on a single machine. The single machine has a maintenance interval,during which no jobs can be processed; each job has a di?erent physical space when it is loaded in the vehicle, and the job needs to be processed on the machine non-preemptively for a certain time; only one vehicle is available to deliver jobs to a customer. The objective of the problem is to minimize the makespan, that is the time which the vehicle returning to the manufacturing center after all jobs are delivered. For this problem, we propose two heuristics with a worst-case ratio of 2 and show that the bounds are tight.In chapter 3, we propose a bin packing algorithm DFFD, in which the items are divided into two groups ?rstly. The algorithm DFFD has wide application background in supply chain management, and the improved approximate algorithm A in the fourth chapter are based on this algorithm. In the algorithm DFFD, the items are divided into any two objects which are disjoint, then assign items to bins by algorithm FFD for items in each object,in order to ensure that the items in the di?erent objects will not be loaded into the same bin. In this chapter, we analyze and prove the worst-case ratio of the bin packing algorithm DFFD.In chapter 4, we propose an improved approximate algorithm for the scheduling problem which is investigated in chapter 2. It is a composite algorithm, in which jobs are divided into batches by NF algorithm and DFFD algorithm. And the worst-case ratio of this algorithm is proven to be not greater than 9/5.In chapter 5, we summarize our results and list several directions for the future research.