Research On Algorithms Of Single Machine Parallel Batch Scheduling Problems

With the development of science and technology, more and more single-job machines are replaced by batch machines. Research on batch scheduling has reached an unprecedented height, and most of the research work are about single machine parallel batch scheduling problems.In this thesis, we study the following single machine parallel batch scheduling problem:There are n given jobs {Ji,J2,…,Jn} Each job Jj has a processing time Pj and a rejection penalty ej (Some job may be rejected for processing. ej is paid if job Jj is rejected). There is a single parallel batch machine that can process jobs simultaneously. The jobs processed together form a batch. All jobs contained in the same batch have the same start time and the same completion time, that is, the start time plus the maximum processing time among the processing times of all the jobs in the batch. Our aim is to determine how to choose jobs for processing, divide these jobs into batches, and sequence these batches so that the objective function is minimized. In this thesis, the objective function is the sum of completion time of the processed jobs plus the sum of rejection penalties of the rejected jobs. We consider two cases:unbounded case and bounded case. In unbounded case, the number of jobs processed in one batch is unbounded, while in bounded case, the number of jobs processed in one batch cannot exceed a constant b.For unbounded model, we first propose an O(n4)-time algorithm by using backward dynamic programming and heap sorting, then improve it to an O(n3 logn)-time algorithm by using geometric induction techniques.Bounded model is more complicated than unbounded model since batches do not satisfy some important rules that batches in unbounded model do. We use backward dynamic programming to reasonably enumerate all the cases to derive an optimal solution in O(n2b2-2b+2)- time, and thus prove that this case can be solved in polynomial time when b is fixed.