Batch Scheduling With Non-Simultaneous Machine Available Time

Scheduling problem is an important research field. Due to its profound significance in both real world and theory, scheduling has always been a hottest topic in the research of combinatorial optimization since the 1990s. Batch scheduling and scheduling with non-simultaneous machine available time are relatively new scheduling models, which are attracting more and more attention recently. In this dissertation, many new results about bathe scheduling with infinite and non-simultaneous machine available time to minimize makespan (C_max) and total weighted completion time (∑ω_jC_j) are presented. Three main chapers are included as follows:In the first chapter, some notations, definitions and basic background information about the subject are introduced.In the second chapter, we present an overall survey on scheduling. The problems of scheduling jobs with non-simultaneous machine available time on parallel identical and uniform batch processing machines to minimize the makespans are considered. Our main results as follows: Used duplicated algorithm, two heuristic algorithms A and A' are designed when the machines' capacity are finite, and the proves that their performance ratios are not more than (2—1/B)[9/7+ (1/2)^k] and 3/5(2-1/B) are proved later.In chapter 3, we considered the problem of minimizing the total weighted completed time on batch scheduling with non-simultaneous machine available time. First of all, we know, the problem with parallel identical machines is NP-hard. It hasn't been widely studied in releted work. We discuss the special case where jobs have constant processing time. An is given, and then proved its optimism. In this chapter, we also design optimal algorithm corresponding to another special case of all jobs with constant release times.