Research On Job Shop Scheduling Based On Immune Principle

Job shop scheduling is one of most complicated combinatorial optimizationproblems and has profound practice background and wide application foreground.Because of ignoring many actual constraints to simplify computation complexity, atpresent scheduling theory research doesn't satisfy the practical application demand.Therefore, it's more significant in theory and valuable in engineering to study the jobshop scheduling close to the production practice, which involves with flexibility,multi-objective, multi-constraint and distributing.In the Dissertation, job shop scheduling is regarded as the research objective, andthe central clue is to close to the production practice, and the technology support is theimmune optimization theory. Several kinds of key technology of job shop schedulinghave been deeply studied, which are modeling, solution, optimization and simulation,et al. The main result and contribution of the dissertation are as follows.1. The modeling methods are put forward. According to the primary clue ofapproaching to the production practice, several kinds of different job shop schedulingmodels are set up, which are the classical job shop scheduling model, the flexible jobshop scheduling model, the multi-objective flexible job shop scheduling model, themulti-constraint nmlti-objective flexible job shop scheduling model and thedistributing multi-objective job shop scheduling model. After analyzing theproduction practice, the dissertations picks up the essence according to the universalprinciple. The physical form and the logic meaning of job shop are depicted by theobjective function and the constraint, and the static characteristic and the dynamicalcharacteristic of job shop scheduling are expressed by the Petri net theory and theobject oriented structure.2. Several kinds of effectual scheduling algorithms are put forward based on themodel and the characteristic of each kind of job shop scheduling. They are dynamicevaluation based immune algorithm, immune simulated annealing algorithm,multi-colony diploid adaptive immune algorithm, immune ant colony algorithm anddistributing scheduling algorithm based on the scheduling grid. These algorithmssimulate many kinds of immune mechanism by using the scheduling model as the application background, the efficiently scheduling as the principle, the immuneoptimization theory as the base. The immune response mechanism includes theimmune detection, the immune learning, the immune remember, et al. The immuneselection mechanism is based on the antibody reproducibility ratio involved with theantibody affinity and the concentration. The immune self-adjusting mechanism isadopted to keep diversity. The vaccine mechanism is used to speed the convergenceand avoid the colony degradation. The instance simulation experiments indicate thatthese algorithms have powerful scheduling optimization capability and can convergequickly, and fit the corresponding job shop scheduling.3. Several kinds of effectual scheduling strategies are put forward. According tothe idea of specifically analyzing the given problem, several multi-objective disposalstrategies are put forward to solve the corresponding job shop scheduling, such asgray correlation analysis method oriented scheduling. The flexible job shopscheduling essentially includes two sub-problems, i. e. the equipment distribution andthe operation scheduling, accordingly the decomposition strategy and the integrationstrategy are used to treat with the flexibility problem. According to the principle ofsimplification and availability, two-level constraint disposal strategy is studied, whichtransforms the constraint into the objective function and filters the candidate solutionsby the constraint conditions.4. The concept of scheduling grid is initially put forward and accordingly thedistributing scheduling method is put forward based on it. The two level schedulingstrategy is put forward which involved with the scheduling among manufacturingcells and the scheduling within the manufacturing cell. The system frame of thedistributing job shop scheduling is established. The task scheduling system is set upand the scheduling implement is constructed. The logic structure of the taskscheduling management is put forward and the process of task schedulingmanagement is confirmed. The mechanism of the bidding and inviting public biddingbased on the immune principle is put forward and the negotiation strategy based onthe matching layer chart is put forward. The multi-objective evaluation system is setup and synchronously optimization is carried out by local scheduling and globalscheduling. The validity of the distributing scheduling method is ultimately proved.5. The solving method of job shop scheduling is established and the key steps aredesigned. The single objective job shop scheduling, the multi-objective job shopscheduling and the distributing multi-objective job shop scheduling are respectivelysimulated and solved with the algorithms put forward. The international classical job shop scheduling instances and the enterprise practice job shop cases are simulated andcontrasted, and the availability of the models and the algorithms are validated.6. Consequently the job shop scheduling system is achieved based on abovescheduling theory with the advanced soft technology, and applied to productionpractice.