Research On Scheduling Problems With Discretely Controllable Processing Times And Rate-modifying Activities

Combinatorial optimization is an important branch of operations research and theoretical com-puter science. Among them, people are keen to discuss one direction is scheduling problem. Generally,scheduling models are considered in a certain characteristics of jobs and machine environment. In re-cent years, with the actual production needs and constantly improve and change constantly, derived several novel scheduling problems. For the characteristics of jobs, people often study whether the ac-tual processing time of a job can be controlled or not. For the machine environment, people consider each machine may require a rate-modifying activity during the scheduling horizon. There are two essential parameters of machine maintenance, i.e., its start time and its duration. If the parameters are different, the scheduling models are also different. Based on the above two aspects, this paper mainly discusses the following scheduling models: single-machine scheduling problems with discrete-ly controllable job processing times and rate-modifying activities, and parallel-machine scheduling problems with discretely controllable job processing times and rate-modifying activities.This thesis consists of the following four chapters.In Chapter 1, we mainly introduce the combination optimization problem, scheduling problem,the basic concepts and the related knowledge on computational complexity. Then we given the comprehensive literature related to our problems.In Chapter 2, we studies the single-machine scheduling problems with discretely controllable job processing times and rate-modifying activities. The duration of the rate-modifying activity on machine is a non-decreasing function of its start time. Given a set of independent jobs J = {J1, J2,…,Jn} to be processed on a machine. In our problem, each job has multiple processing times to be selected. But for different processing times, it requires different processing costs. In addition, we distinguishes two cases: perform the rate-modifying activity or not, and find the optimal schedule, the actual processing time of each job (thereby the corresponding processing cost) and the start time of the rate-modifying activity on machine to minimize the objective function value. When minimize the sum of makespan and total processing cost, we introduce an efficient polynomial time algorithm. When minimize the sum of total completion time and total processing cost and the sum of total earliness, tardiness and common due date and total processing cost, we also introduce polynomial time algorithms.In Chapter 3, we extend to the parallel-machine scheduling problems with discretely control-lable job processing times and rate-modifying activities. Given a set of independent jobs J ={J1, J2, …,Jn} to be processed on m (m < n) unrelated parallel machines (Mi, i = 1,2,… ,m).All the jobs are simultaneously available at time zero. Each job has multiple processing times to be selected in every machine. We are asked to find the optimal schedule, the actual processing time of each job (thereby the corresponding processing cost) and the start time of the rate-modifying activity on machine to minimize the objective function value. When minimize the total machine load cost plus the total processing cost, we propose a algorithm with the computational complexity O(mkn) time.When minimize the total completion time cost plus the total processing cost, we propose a algorithm with the computational complexity O(nm+4) time. When minimize the total earliness and tardiness costs plus the total processing cost, we also propose a algorithm with the computational complexity 0(mkn2 + nm+4) time.The fourth chapter summarizes the whole paper, and gives the direction and content that we need to continue to explore in the future.