OPTIMIZATION METHOD FOR A JOB – SHOP SCHEDULING PROBLEM WITH ALTERNATIVE MACHINES

IN THE BATCH PROCESS

Pan Quanke

(College of Computer Science, Liaocheng  Univercity, Liaocheng 252000 )

Zhu Jianying

(College of Mechanical & Electrical Engineering, Nanjing University of Aeronautics and Astronautics, Nangjing 210016)

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: Job shop scheduling  Genetic algorithms  Batch process

CLC No: F406

国家自然科学基金资助项目(59990470). Received 30408, received in revised form 20031015