On Batch Scheduling Models

Batch scheduling is one of significant modern scheduling models that advances rapidly in recent years. It is motivated by important applications. Batching means that sets of jobs which are processed on the same machine must be grouped into batches. The finishing time of all the jobs in a batch is defined to be the finishing time of the last job in the batch. The goal of batch scheduling is to partition jobs into batches and schedule the batches such that the objective function is optimized. Batch-scheduling models go into two categories by the way of batching: parallel- batch scheduling and serial-batch scheduling. For the parallel-batch (p-batch) scheduling model, the machine can handle more than one job at a time, while for the serial-batch (s-batch) scheduling model, it can handle at most one job at the same moment so that the jobs in a batch must be processed one by one in a serial order.Hierarchical criteria scheduling, as a way of multi-objective decision-making, plays an important role in solving complicated problems arising from economics, administration, engineering, etc. For example, a factory administrator needs to arrange the jobs to be processed such that the total completion time is minimized firstly to reduce the processing cost, and the tardy jobs are limited to a lowest level secondly to satisfy the clients. The optimality principle of scheduling problems with hierarchical criteria is: For a scheduling problem with k criteria, to find its optimal solution is to find the optimal solution of the problem with kth criterion among the set of optimal solutions of the problem with the earlier k — 1 criteria. Very few researches on hierarchical criteria scheduling problem are reported in literatures at present. Lee presented some algorithms and complexity analysis for some problems in this aspect, with the first criterion of ∑ C_j, ∑ w_jC_j, T_max and ∑U_j, respectively.Just-In-Time(JIT) scheduling is a classical scheduling model, for which much research work has been done and significant progresses have been made so far. The model is characterized by a rigorous rule that all jobs must be completed exactly on their assigned due dates, otherwise penalty must be executed, both for earliness...