A Kind Of Parallel Machine Scheduling With Industrial Bound Using Genetic Algorithm

The job shop scheduling problem (JSSP) is a kind of typical productive scheduling problem, and it has a full background of engineering-based project which can usually be conversed to applied project problems. Recently, according to the development of advanced technical support, the meaning of job shop scheduling problems has changed a lot: stochastic, dynamic, bounded, multi-object, these words are added on to describe it. Parallel machine scheduling (PMS) takes place usually in a factory environment where different tasks must be processed to complete a job. A number of jobs are being processed at any one time on a number of machines. A scheduling must be derived from a given production configuration that aims to finish all jobs as rapid as possible. The job shop scheduling problem has been studied for decades and known as an NP-hard problem. The parallel job shop scheduling problem is a generalization of the classical job scheduling problem that allows an operation to be processed on one machine out of a set of machines. The problem is to assign each operation to a machine and find a sequence for the operations on the machine in order that the maximal completion time of all operations is minimized. A genetic algorithm is used to solve the parallel job shop scheduling problem. A novel gene coding method aiming at job shop problem is introduced which is intuitive and does not need repairing process to validate the gene. Computers emulations are carried out and the results show the effectiveness of the proposed algorithm.