Multi-objective Flexible Job Shop Scheduling Problem: Simulation Approach
Conférence : Communications avec actes dans un congrès international
In traditional Job Shop Scheduling Problem (JSP), there are n jobs and machines in manufacturing system, where each job consists of j operations that need to be executed on machines by a given order. Flexible Job Shop Scheduling Problem (FJSP) is an extension of classic JSP. It extends the assumption that only one machine is able to run a particular operation.
Since JSP can be considered as a special case of FJSP and JSP is well-known NP-hard, FJSP is also regarded as an NP-hard problem.
Considering its computational complexity, various metaheuristic have been extensively applied to FJSP. Zendieh et al.[9] proposed a Genetic Algorithm by using several different rules for generating the initial population and several strategies for producing new population for next generation. Gao et al.[6] introduced a Pareto-based grouping discrete harmony search
algorithm (PGDHS) to solve FJSP. Chamber et al. [1]extended their Tabu Search strategy previously described for job shops and applied it to FJSP. Besides metaheuristic algorithm,
researchers also employ traditional polynomial algorithms and hybrid algorithms[5] in FJSP.
The objective of Flexible Job Shop Scheduling Problem is to determine a feasible schedule S by minimizing a given objective function [4]. In early work, the wide-used objective is from a single dimension, considering only one objective once. Recently, researchers [5][10] have addressed their study on multiple objectives.
In this paper, a novel dynamic scheduling algorithm based on simulation environment is proposed to schedule transportation tasks in FJSP with five objectives, such as the minimization of
makespan and transportation distance. The dynamic algorithm, we proposed in this paper, is developed from a previous study in the LINEACT laboratory[2][3][7][8]. We improve the decision
process in order to avoid being trapped in local solutions, and the novel dynamic algorithm makes it possible to get schedule results from the simulator directly.