نوع مقاله : پژوهشی
1 گروه مهندسی صنایع - دانشگاه بوعلی سینا همدان
2 گروه مهندسی صنایع - دانشگاه آزاد اسلامی واحد کرج
عنوان مقاله [English]
Scheduling for flexible job shops is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem in medium and actual
size problems with traditional optimization approaches, owing to the high complexity of computations. The flexible job shop scheduling problem (FJSP) extends the job shop scheduling problem (JSP) by assuming that, for each given
operation, there is at least one instance of the machine type necessary to perform it. The scheduling problem of a FJSP consists of a routing sub-problem, i.e., assigning each operation to a machine out of a set of capable machines,
and the scheduling sub-problem, i.e., sequencing the assigned operations on all machines, in order to obtain a feasible schedule minimizing a predefined objective function.
The FJSP mainly presents two difficulties. The first is to assign each operation to a machine, and the second is to schedule these operations in order to make a predefined minimal objective. The FJSP is a much more complex version
of the JSP, so the FJSP is strongly NP-hard and combinatorial. It incorporates all of the difficulties and complexities of its predecessor, JSP, and is more complex because of the additional need to determine the assignment of
operations to machines.
This paper attempts to simultaneously optimize three objectives, including minimization of the makespan, total workload and critical workload. Since the multi objective flexible job shop scheduling problem is strongly NP-Hard, an
integrated heuristic approach is used for solving it. The proposed approach is based on a floating search procedure that uses some heuristic algorithms. The floating search procedure uses local heuristic algorithms, which make the
considered problem into two sub problems, including assigning and sequencing sub problems. Then, a search is done on the assignment space. After achieving an acceptable solution, a search is done on the sequencing space, based on a heuristic algorithm.
This paper used a multi-objective approach for producing a pareto solution. This proposed approach is adapted from the NSGA II algorithm and evaluates pareto-archives. The elements and parameters of the proposed algorithms are
adjusted based on preliminary experiments. Then, computational results are used to analyze the efficiency of the proposed algorithm.