Some Problems Of The Batch Scheduling And Scheduling With Availability Constraints

Scheduling is an important branch of combinatorial optimization. Due to its bright applicable background and great theoretical significance, the schedul-ing theory extensively has been applied in many areas, such as production of industry and agriculture, transportation, management science and computer sci-ence, etc. Both parallel-batch scheduling and scheduling with machine availabil-ity constraints are relatively new scheduling models, which have attracted great attention of scholars both at home and abroad. In the classical scheduling, it is assumed that the processing times of jobs are constant. However, there are many situations where the processing time of the job depends on its starting time or its position in the sequence. So that, the modern scheduling with varying processing time emerged. In this dissertation, some new results on the parallel-batch scheduling with processing time of constant or variable and scheduling with machine availability constraints are presented.1. In chapterⅠ, we introduce the background of scheduling and some basic fundamental knowledge.2. We consider the parallel-batch scheduling with constant processing times in ChapterⅡand ChapterⅢ. In ChapterⅡ, we discuss the unbounded parallel-batch scheduling model of minimizing the total weighted completion time on parallel uniform machines. We present some properties of the optimal schedule and design an O(nm+2) time dynamic programming algorithm when the num-ber of machines m is fixed. In ChapterⅢ, we address the unbounded and bounded parallel-batch scheduling models on parallel unrelated machines. For the unbounded model, with the assumption that the processing times of jobs are agreeable, we design O(nm+2) time dynamic programming algorithm in polyno-mial time to minimize the total completion time. For the bounded model, with the assumption that pij= pi (1≤i≤m,1≤j≤n), we design optimal al-gorithms and pseudo-polynomial time algorithms for the minimizations of some different objectives. 3. We consider the parallel-batch scheduling with varying processing times in Chapter IV and Chapter V. In Chapter IV, the processing time of job Jj (j= 1,…, n) is pj=αjt, where aj is defined as the deteriorating rate, t is the starting time of Jj. We discuss the minimizations of the maximum completion time and the total completion time. To minimize Cmax, we present an optimal algorithm and an FPTAS for the single-machine issue and multi-machine issue when all the jobs have identical release dates, respectively. Furthermore, we prove that the single-machine parallel-batch scheduling is NP-hard when the jobs have distinct release dates and design an optimal algorithm for one special case. To minimize (?)=1Cj, we design a pseudo-polynomial time algorithm when the number of deteriorating rates m (0. The objective is to minimize the maximum completion time of acceptd jobs and the total penalty of rejected jobs. We show that this problem is NP-hard and provide a pseudo-polynomial time algorithm and an FPTAS.4. In chapterⅦ, we consider the scheduling under mixed deterioration with machine availability constraints. The processing times of some jobs from this job set are constant, while other ones are simple linear functions of the job starting times. The objective is to minimize the maximum completion time. Assuming that the machine has only one non-availability interval, we prove that the single-machine issue is NP-hard in the ordinary sense and design an approximation algorithm with worst performance ratio 4/3. Furthermore, we prove that the multi-machine issue is strongly NP-hard.