Batch Scheduling Problem With Controllable Processing Times

Scheduling problems, batch scheduling with controllable processing times have deep roots in the real world. In batch scheduling problems, B jobs can be processed on the machine at most, and they are not allowed to be interrupted, removed, or added a new job during processing. In the controllable processing time problems, time parameters of jobs may not be fixed, so we can compress the original processing time, and reduce the corresponding pressure cost. In this paper, we combine above two kinds of the modern sorts, discuss the batch scheduling with controllable processing times problem. The structure of the thesis is arranged as follow:In the first chapter, we mainly introduces some notations, definitions and basic background information of the scheduling problem. Some useful information and the main results are obtained in this thesis.In the second chapter, we consider the problem of jobs with dynamic arrival times and of jobs with the processing times can be controlled. The object is to minimize the maximum completion time and controllable costs of processing time. Under the condition that there are constant dynamic arrival times, we design dy-namic programming algorithm, which can be solved in O(mn(Bhphpsum)m-1),where n is the number of jobs,m is the number of distinct job release times, there are B jobs at most can be processed in the same time, it has h different process times for every job,ph is the maximum job times,psum is the sum of job processing times. Further analying the more general situation, we design FPTAS algorithm.In the third chapter, we study the problem of jobs with dynamic arrival times, of jobs can be interrupted during processing, and can be scheduled in two machines whose speeds are differents. The object is to minimize the total completion time. This problem is NP-hard, we analyze special cases, namely when the jobs are scheduled in the next moments, two machines are all idle, or are all busy, and MSPT generated is optimal sorting algorithm, this algorithm produces 2N times interrupted mostly, and it can be solved in O(Nn logn) times.