Problems Of Bicriteria Serial Batch Scheduling On A Single Machine

Scheduling theory, which is also called the timetable theory, is a kind of important combinational optimal problem and an active branch in study of the operations research. so it has very broad applied prospect. In recent years, batch scheduling and multicriteria scheduling have have been more and more concerned as two new models of morden scheduling. In this dissertation, we mainly discuss two special problems of bicriteria serial batch scheduling on a single machine, combining these two models together.Three main chapters are included as follows:In the first chapter, some notations, definitions and the basic background about the subject are introduced. And then the main reserach results about this dissertation have been summaried.In the second chapter, one kind of bicriteria models of scheduling n jobs on a single unbounded serial-batching machine, the constrained model are studied. We mainly concern some common functions as the objective functions, such as Cmax, Lmax,∑Cj. We present a corresponding dynamic programming algorithm for each model and analyze their complexities. In the end, we prove that the restricted model we studied in this paper is much more general than the primary-secondary criteria scheduling model.In the third chapter, we mainly consider a special class of Pareto optimal problem, in which the objective functions are Cmax and∑Cj), respectively. We present the Pareto Optimal schedule for this problem.And further more,we find all the Pareto Optimal points. In the end,wo analysis the computitional complexity,which is O(n3).