Several Scheduling Problems With Resource Controllable Processing Times

Scheduling is an important branch of combination optimization problems which has a profound background and a wide applied prospect. In traditional scheduling problems, it is assumed that the job processing times are fixed. However, in practical manufacture, the processing time of each job may depend on some factors such as its starting time, its position in a scheduling or the actual resource allocation to it.In chapter 1, we mainly introduce the background, the current situation of scheduling problem and present our works in this paper.In chapter 2, we mainly study single machine due-window assignment and scheduling with controllable job processing time. The actual processing time of each job is a convex function of the amount of the resource allocated to the job. Simultaneously, we also consider both the position-dependent learning effect and linear time-dependent deteriorating effect. Each job has an independent due-window, but all the jobs share the common window size. We have to determine the job sequence, due-window starting times, window size and the resources allocation to minimize an integrated objective function which includes weighted earliness, the weighted number of tardy jobs, due-window starting times, window size, resource cost and the makespan cost. We provide an optimal polynomial time algorithm for the considered problem.In chapter 3, we study parallel-machine due-date assignment problem and scheduling with linear deteriorating jobs, the actual processing time of each job is a linear function of the starting time. Each job has an independent due-date, jobs completed before or after the due-date are penalized according to their earliness or tardiness values. Rejection is allowed in this problem, if a job is rejected, a certain amount of rejection fee must be paid. The objective is to determine the optimal scheduling and due-date of the accepted jobs to minimize the sum of due-dates, the weighted number of tardiness jobs, the total completion time and the rejection cost. We Show that the NP-hard problem can be solved by a dynamic programming, finally, a fully polynomial-time approximation scheme(FPTAS) in O (n~5D~2/ε~2) time is given for the problem, where n is the number of the jobs, ε is the error bound,D=max{lna_max,ln(1+b)}.In chapter 4, we study the scheduling problem of production and transportation in a two-stage supply chain, where job processing time is a convex resource consumption function. Under serial batching availability, a set of jobs is processed contiguously and completed together when the processing of the last job in the batch is finished. Then, the batches are delivered to a customer by a single vehicle with limited capacity during the transportation stage, and the vehicle can only deliver one batch at one time. We consider the two-resource allocation case, and provide an O (n~2logn) or O(n~2lognlog(1/ε))algorithm to make decisions on job batching and batch sequencing and the resource allocation to minimize the makespan.Finally, we summarize this paper, and provide problems needed to study in the future.