Scheduling Problems With Job Processing Flow Optimization

Scheduling is an important research field of combinatorial optimization.It is widely used in scientific management,computer science,industrial and agricultural production,transports and other sectors.It has been attraced the attention of academic circles in both at home and abroad.The objective of this paper is to minimize the delivery time and the batch scheduling problems with job processing times are the same.There are three chapters in this paper.In the first chapter,some notations,definitions and basic backgrond informations about thc subject are introduced.In the second chapter,we present some on-line algorithms to minimize the delivery time on a single batch processing machine when batch size is infinite and off-line algorithm when jobs have the same processing times.Our objective is to minimize the delivery time,which is thc sum of the job completion time and transportation time.We present three on-line algorithms for this problem.At the same time,we prove that the competitive ratio of the first two algorithms is at least 2.These two algotithms can also solve the problem if jobs have the same processing times and the same transportation times optimaly. Simultaneously,the first algorithm is also best possible algorithm if the problem has agreeable(r_j,p_j,q_j).When processing times and transportation times are agreeable,we give an on-line algorithm whose competitive ratio is 1.618,at the same time it is also the strongest possible on-line algorithm for the problem.At last when jobs have the same processing times and the number of job release times is a constant,we present a polynomial time algorithm.In the third chapter,we conside the scheduling problem with batching delivery if job processing times are equal.If batching is not allowed in deliverying, we provide an optimal algorithm for it,whose time complexity is O(nlogn).For the general problem,we present an approximation algorithm with a competitive ratio B.We also provide a dynamic programming algorithm and analysis its time complexity.