On Several Problems Of Bicriteria Batch Scheduling On A Single Machine

Scheduling theory, which is also called the timetable theory, has been developed to be a branch of the operations research and an applied science. It has profound practical and broad applied prospect. In recent years, modern scheduling problems have been studied widely, among which batch scheduling and multicriteria scheduling have attracted the attention of so many scholars at home and abroad because of their obviously factual meanings. In this dissertation, we mainly discuss several special problems of bicriteria 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, two kinds of bicriteria models of scheduling n jobs on a single unbounded parallel-batching machine, the constrained model and the linear weighted model, are studied. We mainly concern some common function as the objective functions, such as C_max,L_max,∑w_jC_j. 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 primary-secondary criteria scheduling problems, in which the primary criteria is∑w_jC_j,and the secondary criteria is C_max. We present a dynamic programming algorithm for a single unbounded parallel-batching machine and analyze their complexities. As to the bounded model, we consider a special case that all jobs with equal processing time on m parallel-batching machines, we also present an approximate algorithm and prove that its worst case performance ratio is 2-1/m.