Single Machine Scheduling Problems With Controllable Processing Times

Scheduling problem is an important class of combinatorial optimization problem. It can be described as using some machines under certain conditions, with a minimum of time, or at least the cost to complete the given task. In traditional scheduling problems, the processing time of a job is assumed to be a fixed constant. However, there are many actual production environments, where the processing times of jobs may be subject to change due to deteriorating effect, resource allocation or machine maintenance and other factors. This article focuses on three types of single machine scheduling problem with controllable processing times. The main content is as following:In the first paper, we firstly introduce the definition of scheduling problems and the three-field notation. In addition, we describe the present research of the scheduling problem with controllable processing time and present our innovation work on this basis.In chapter 2, we investigate the scheduling problems of a single serial-batching machine with deteriorating setup time and deteriorating job processing times. With the assumption of deteriorating jobs, the job processing times are described by an increasing function of their starting times. All the jobs are first partitioned into serial batches and then processed on a single serial-batching machine. Before each batch is processed, deteriorating setup time is required. We propose an optimal algorithm to solve the problem of minimizing the makespan and the maximum lateness.In chapter 3, we study the single machine scheduling problem, where both setup and job processing times are controllable by allocating a continuously divisible nonrenewable resource. The processing time of jobs is a function of deterioration effects and resource allocation. Before each job is processed, a setup time is required, it is a convex function of resource allocation. We propose an optimal algorithm to solve the problem of minimizing the makespan.In chapter 4, we consider single-machine due window assignment and scheduling with a common flow allowance, resource allocation, and a deteriorating rate-modifying activity, subject to unlimited or limited resource availability. Due window assignment with a common flow allowance means that each job has a job-dependent due window, the starting time and completion time of which are equal to its actual processing time plus the job-independent parameters 1q and 2q, respectively, which are common to all the jobs. We assume that the processing time of a job is a function of the amount of a resource allocated to it, its position in the processing sequence, and its deteriorating effect. The objective is to minimize the total cost, which is a function of earliness, tardiness, due-window starting time, due-window size, and resource consumption. We consider two models of the job processing time function and provide polynomial-time solution algorithms for the corresponding problems.