An immune algorithm for batch job-shop scheduling with multi-objectives

Job-shop scheduling is a difficult type of production planning problem, of which the primary characteristic is that the processing route of each job is different. Mostly, more than one workpiece of each type are to be produced in practical production. Thus makes the batch job-shop sequencing problem more important, although there is little literature concerning it. In most studies on job-shop scheduling problems, the objective is usually to determine the sequence of jobs to minimize the makespan. The delay time of jobs, the availability of key machine and the average queuing time of jobs are also the objectives to be considered synthetically in real manufacturing process. In this paper, a batch job-shop scheduling problem with multi-objectives is studied. First, the description of this problem is given with its model and the mathematical model of the multi-objectives. Then, it is proposed how to decide the starting time of jobs on machines under different move ways. An immune algorithm based on the biological immunity mechanism is used to solve this problem. Finally an illustrative example is tested on the software programmed according to this algorithm. The results show that the immune algorithm proposed can solve batch job shop scheduling with multi-objectives and it is important to consider batch during scheduling.