Two Batch Scheduling Models On A Single Batch Machine

Due to its profound significance in both real world and theory, scheduling has always been a important branch of Operational Reseach. Batch scheduling is relatively new scheduling model, which are attracting more and more attention recently. How to maximize the weighted number of jobs completed in due date windows, how to minimize the total processing cost are very important in modern management. In this dissertation, many new results of the above two models on algorithms are presented:1. In modern management, it is very important to arrange jobs reasonably so as to enable delivery in time. Early completed job or late completed job will increase costs. The scheduling problem that maximize the weighted number of jobs completed in due date windows is NP-hard. In this paper, the bathing machine scheduling problem of maximal number of jobs completed in due date window is discussed. When D_j~2—D_j~1 < p_j, an dynamic programing algorithm solving this problem is given.2.In this paper, We consider a batch scheduling model in a single machine. During processing, no tardiness jobs are allowed, so only earliness penalties and machine processing cost are to be considered, the objective function is to minimize the total cost, when , we present a polynomal algorithmwhich can obtain the optimal scheduling when the capacity of the maching is infinite.