Research On Batch Processing Machine Scheduling With Non-identical Job Sizes

Unlike traditional machines, batch processing machines can simultaneously process several jobs (or tasks) as a batch. Batch processing machines have important applications in many industries such as electronics manufacturing facilities, steel industry, aircraft plants and so on. Effective scheduling batch processing machines can significantly improve the productive efficiency of enterprises and reduce the production cost. Hence, studying batch processing machine scheduling problems has not only great theory value, but also urgent practical significance.Jobs with non-identical sizes can be often found in manufacturing shops. While most of early research assumes jobs with identical sizes. This paper considers batch processing machine problems with non-identical job sizes. Compared with the case of identical job sizes, our model is more general and complex. It is a combination of the sequencing problem and packing problem.The major contributions of this paper are as follows:(1) The single batch processing machine problem with non-identical job sizes and unequal release times is studied. The objective is to minimize makespan. This problem is NP-hard. First, we propose two lower bounds for the problem and prove the validity of them. Then, several construction heuristics are developed from a new point. Job processing times and release times are usually contradictory when making decisions to form batches. This is indeed a challenge for solving batch scheduling problems. So most heuristics consider only a single factor in determining the jobs of each batch. However, our heuristics attempt to make a trade-off between job release times and processing times and hence can take both factors into account to form batches. A distance matrix is built. Several construction heuristics are proposed based on the distance matrix to group jobs into batches; then the ERT rule is applied to schedule the batches on the machine. Computational simulation and comparisons with some existing algorithms demonstrate the effectiveness of the proposed lower bounds and heuristics.(2) A two-stage flowshop with non-identical job sizes, arbitrary release times and blocking is considered. The objective is to minimize makespan. First, a mixed integer programming model is formulated for this problem. Then, a hybrid discrete differential evolution (HDDE) algorithm is proposed. In this algorithm, individuals in the population are represented as discrete job sequences. New mutation and crossover operators are developed based on this representation. The first-fit rule is employed to form batches; then a least idle/blocking time heuristic is proposed to schedule the batches in the flowshop. In order to enhance the exploitation ability, a local search method is embedded in the algorithm. Computational experiments demonstrate the superiority of the HDDE algorithm in terms of solution quality, robustness and run time.(3) A two-stage flowshop with unequal job sizes, comprised of a parallel batch processing machine and a serial batch processing machine, is examined. The objective is to minimize makespan. We build the mixed integer programming model for the problem. Then a population-based evolutionary method named estimation of distribution algorithm (EDA) is proposed. Firstly, the individuals in the population are coded into job sequences. Then, a probabilistic model is built to generate new population and an incremental learning method is developed to update the probabilistic model. Thirdly, the best-fit heuristic is used to group jobs into batches and a least idle/waiting time approach is proposed to sequence the batches on batch processing machines. In addition, some problem-dependent local search heuristics are incorporated into the EDA to further improve the searching quality. Computational experiments demonstrate the effectiveness and robustness of the proposed EDA.