Research On Multi-objective Flexible Job Shop Scheduling Problem

The classical job shop scheduling problem (JSP) has always being studied byresearchers and therefore abundant theories are yielded through the past half centuries.However, they are hard to put into practice because of the unrealistic assumptions insetting up the model of JSP. Multi-objective flexible job shop scheduling problem(FJSP) is an important extension of JSP, which takes into account not only theflexibility of machine availability but also the different expectations from differentdepartments. Therefore, research on the multi-objective FJSP is significant both intheory and in practice.The multi-objective FJSP is studied thoroughly and systematically. The maincontent and the contribution are as follows.1. A scheduling performance evaluation criteria system for FJSP is presented,including the Makespan criterion, the production cost criterion, the machine workloadcriterion and the due date criterion. Especially, a scheduling evaluation orientedcosting model is set up and the procedure to evaluate scheduling decision is putforward for the production cost criterion.2. A two-phase optimization model, i.e. the optimization phase and the decisionmaking phase, is proposed for the multi-objective FJSP problem. In the optimizationphase, a Pareto set is achieved through a multi-objective optimization algorithm. Inthe decision making phase, the Pareto set is evaluated with a multiple criteria decisionmaking method.3. A multi-objective immune genetic algorithm (MOIGA) combining the immunealgorithm with the multi-objective genetic algorithm is presented for the generalmulti-objective FJSP. An extended operation-based encoding method is proposed inMOIGA and a base of scheduling algorithms for FJSP is formed.4. The time complexity is computed to show the feasibility of MOIGA and therelated factors are discussed. Markov chain is used to prove its convergence to theoptimal Pareto frontier with the probability of one. The incremental mutation rate and the niche technology ensure the diversity of the Pareto solutions.5. A multi-criteria decision making method integrating the analytic hierarchyprocess with the fuzzy evaluation (AHP-FE) is put forward to evaluate the Pareto set.The fuzzy evaluation method structures the fuzzy judgment matrix and the decisionmatrix, which makes UP the subjective deficiency of the AHP.6. A new type of multi-objective FJSP problem with objectives different amongjobs is studied to further make the scheduling decision more practical. In theoptimization phase, a MOIGA-â… optimization algorithm is proposed. In the decisionphase, a job weight based AHP-FE decision method is used to evaluate the Paretosolutions.7. The multi-objective dynamic FJSP with objectives changing between thepre-scheduling and the rescheduling is modeled and an event-driven andperiodic-driven based dynamic scheduling strategy is proposed. A modifiedMOIGA-â…¡optimization algorithm is designed. The simulation of multi-objectivedynamic FJSP in a situation that quality problem occurs proves that MOIGA-â…¡cansolve the problem effectively and efficiently.8. A B/S structure based prototype is developed on the base of the above research.The running result in an aeronautic company shows the favorable effect in theplanning and scheduling management.