The Machine Has A Non-available Period Of Time To Reject The Sorting Problem

As the needs of actual production, the machine may not work during some time. So the application of scheduling problem with machine availability constraints has received more and more attention. Besides, the manufacturers begin to select jobs and they try their best to choose the jobs which will bring greater profits. At the same time, they will reject jobs with longer processing time but lower profits, and they can also outsource these jobs to the other companies to process. Of course, the machine is not available all the time, as the workers have their own work hours and the machine needs repair or maintenance. The machine can’t process jobs during rest time of the workers and the machine maintenance time or time for parts replacement. And according to the specific needs, the processing time of jobs may follow deteriorating effect. As part of the supply chain, the manufacturers need not only to process jobs but also to deliver the completed ones to the customers as soon as possible. Definitely, they can choose the-third-party logistics enterprise to help them deliver them. With the development of times and the need of actual production life, the problem of how to accept jobs rationally, arrange them to process and batch delivery in order to improve the customer’s service level as well as minimize the delivery time has received more attention.In chapter one, the author mainly introduces the basic knowledge of the scheduling problem, the main concept and the common sense in combinatorial optimization. And the author introduces the basic knowledge of the scheduling problem with availability constraints and rejection, besides the supply chain scheduling problem. Finally, the author illustrates the research status quo of this problem and the main result of this paper.In chapter two, the author studies a two-parallel-machine scheduling problem with a fixed availability constraint on one of the machines. Jobs can be accepted and arranged on the machines to be processed or rejected. Our objective is to minimize the makespan of the accepted jobs plus the total penalties of the rejected jobs. The two main model are shown in the following:(Ⅰ) If the jobs must restart processing after the interval, we have solved it by a dynamic programming algorithm.(Ⅱ) For the resumable case, this section has presented the pseudo-polynomial dynamic programming algorithm.In chapter three, the author has considered m parallel machines scheduling problem with rejection, and there is a planned maintenance period on each machine. The author mainly studies the following two models:(Ⅰ) Jobs must restart processing after the interval, and the manufacturer is allowed to accept the jobs or reject/outsource them by paying penalties. The objective is to minimize the total completion time of the accepted jobs plus the total penalties of the rejected ones. We can solve the above problem by a dynamic programming algorithm.(Ⅱ) Jobs must restart processing after the interval. And we can select the certain orders to process. Besides, the starting time of jobs is a simple linear function of its starting time. The objective is to minimize the total weighted completion time of the accepted jobs plus the penalties of the rejected jobs. In this section, we present a dynamic programming algorithm.In chapter four, the author studies the single machine scheduling problem with a fixed availability constraint. Rejection is allowed, and the completed jobs need to be delivered to one customer. The author mainly considers the following three models:(Ⅰ) The jobs are processed on a single machine, and rejection is allowed. Jobs interrupted by the interval can resume processing after it. The processing time of the jobs is a linear function of its basic processing time and its starting time. And the completed jobs need to be batch delivered to the same customer. There are sufficient available vehicles to deliver jobs and each vehicle has a capacity constraint. The objective is to minimize the delivery time of the last batch to the customer plus the transportation cost and the penalties of the rejected jobs. In this section, we present a pseudo-polynomial dynamic programming algorithm.(Ⅱ) Jobs are processed on a single machine which has a fixed availability constraint. And the jobs which can’t be finished before the unavailable period can continue processing after it. Rejection is allowed and the completed jobs need to be batch delivered to the same customer. Besides, the number of the vehicles is infinite and the capacity is limited. The objective is to minimize the total delivery time and transportation cost of the accepted jobs plus the total penalties of the rejected ones. The above problem can be solved by a dynamic programming algorithm.(Ⅲ) Jobs are processed on a single machine with a fixed availability constraint. In addition, jobs can resume processing after the interval, and rejection is allowed. The completed jobs must be delivered individually and immediately. In addition, there are sufficient vehicles and the capacity is 1. Every job has a due date, and the objective is to minimize the maximum lateness, transportation cost and the penalties of the rejected jobs.This section presents a pseudo-polynomial dynamic programming algorithm.