Abstract: The job-shop scheduling problem with alternative machines in the batch process is investigated. The heuristic based operation precedence is developed to address the reduction of makespan. Then a new hybrid procedure is presented by combining the heuristic with Genetic algorithms. In the procedure, Genetic algorithms derive the optimal chromosome and the heuristic turns the chromosome into the optimal scheduler. The strategies to improve productivity are three：first, before-arrival setup time is separated from processing times, then the setup is prepared before the job’s arrival. Second, the original batch is split into many smaller batches, and every smaller batch is regarded as a single part. Finally, the jobs are transferred to successive machine while a division of batch is finished, so the latency time of the machine is reduced. An example of scheduling is given, and the results show that the method is available and efficient.

Key words: Batch process, Genetic algorithms, Job shop scheduling