查看文章

A job shop consists of a set of different machines (like lathes, milling machines, drills etc.) that perform operations on jobs. Each job has a specified processing order through the machines, ie a job is composed of an ordered list of operations each of which is determined by the machine required and the processing time on it. There are several constraints on jobs and machines:(i) There are no precedence constraints among operations of different jobs;(ii) operations cannot be interrupted (non-preemption) and each machine can handle only one job at a time;(iii) each job can be performed only on one machine at a time. While the machine sequence of the jobs is fixed, the problem is to find the job sequences on the machirres which minimize the makespan, ie the maximum of the completion times of all operations. It is well known that the problem is NP-hard (Lenstra and Rinnooy Kan, 1979) and belongs to the most …