Multi-objective Batch Scheduling And Its Related Topics

Machine scheduling has been one of the most active research topics in combinatorial optimization over the last half century.However,most of the classical scheduling literatures consider that the machine can process at most one job at a time,and consider only one objective.Scheduling on batching machines and multicriteria scheduling problems have been studied extensively in recent years.Yet it seems that only little work have been done in their intersection part,that is,multicriteria scheduling on batching machines.This situation cannot satisfy the real-life need due to the rapid development of semiconductor manufacturing and other areas.It is necessary to consider multicriteria scheduling on batching machines in order to give better service to reality.Suppose that we are given n independent jobs J₁,J₂,...,J_n.They are to be scheduled on a single batching machine.The processing time,due date,deadline and weight of job J_j are p_j,d_j,(?)_j and w_j(j=1,...,n),respectively.And we use S_j and C_j to denote the starting time and the completion time of job J_j.For a given scheduleσ, L_j(σ)=C_j(σ)-d_j and L_max(σ)=max_j=1ⁿ L_j(σ) are defined as the lateness of job J_j and the maximum lateness ofσ,respectively.T_j=max{0,L_j} is the tardiness of job J_j,and U_j is its unit penalty.In this thesis,we focus on minimizing bicriteria scheduling problem on a batching machine.A batching machine is a machine that can handle up to b jobs in a batch.The jobs in a batch start and complete respectively at the same time.According to the difference of the processing time of a batch,batching machine is divided into parallel-batching machine and series-batching machine.In parallel-batching machine, the processing time of a batch is equal to the largest processing time of jobs in the batch. This model is motivated by the burn-in operations for semiconductor manufacturing, computer system and other areas.In series-batching machine,the processing time of a batch is equal to the sum of the processing times of jobs in the batch.In addition,there is a constant setup time s for each batch.This model applies to a lot of fields.For example, after a batch is processed,people often take a span to change tools,repair machine and so on.On the other hand,two objective functions may represent different interests of two decision-makers.The basic motivation of this direction is that quality evaluation is a multidimensional notion and decision-makers usually pursue several performance criteria simultaneously-to find all Pareto optimal schedules.A feasible scheduleσis Pareto optimal,with respect to the performance criteria f and g if there is no feasible scheduleÏ€suchthat both f(Ï€)≤f(σ) and g(Ï€)≤g(σ),where at least one of the inequalities is strict.The main results of this thesis are as follows:1.Bicriteria scheduling on a parallel-hatching machinePrevious researchers have showed that the problem of minimizing maximum lateness and maximum cost criterion on a machine is solvable in O(n³ log n) time.For the parallelbatch scheduling problem,when the batch capacity of the machine is unbounded,we have known a dynamic programming algorithm that requires O(n²) time for minimizing the maximum lateness.We study the bicriteria problem of scheduling on a batching machine to minimize maximum lateness and makespan simultaneously,and presented an O(n³) algorithm,and it is a complete solution.In addition,when the batch capacity of the machine is bounded,and the processing times of all jobs are equal,some hierarchical minimization problems with total tardiness as the primary criterion,the number of tardy jobs or the weighted number of tardy jobs or the total weighted completion time as the secondary criteria,have O(n³) algorithms.We present O(n log n) algorithms so as to improve the time bounds.2.Bicriteria scheduling on a series-batching machineFor the series-batch scheduling problem,when the batch capacity of the machine is unbounded,the problem of minimizing the maximum lateness has an O(n²) algorithm; the problem of minimizing the total weighted completion time has an O(n) algorithm. We present an O(n²) algorithm for the problem of minimizing maximum lateness and makespan simultaneously.Moreover,for the problem of minimizing makespan and the total completion time,we find all Pareto optimal schedules in O(n²) time for unbounded and bounded models,respectively.3.Bicriteria scheduling on a machineWe have known that the single machine scheduling problem of minimizing the number of tardy jobs,with deadline constraint,is NP-hard.Some O(n²) backwards schedule algorithms have been presented for the following special cases:(â…°) di≤d_j implies(?)_i≤(?)_j and Pi≤P_j; (â…±) p≥p_j implies d_i-d_j≤p_i-p_j. To establish a uniform theory,we propose a dual approach-the forwards greedy algorithms. For case(â…°),it has a better time bound O(n log n).For case(â…±),it has the same time bound,but has different features.Moreover,And we study the case with the identical processing time,and present an algorithm with time bound O(n log n) as well.Since different decision-makers may have different due dates for a job(they represent their individual expected interests),we may suppose that each job J_j has two due dates d_j⁽¹⁾ and d_j⁽²⁾(1≤j≤n).Thus for a given schedule a,two objective functions of maximum lateness L_max⁽¹⁾ and L_max⁽²⁾ are induced.We proved that minimizing two maximum lateness simultaneously,with respect to two sets of due dates,is solvable in O(n³ log n) time,and the time bound is tight.