A Particle Swarm Approach for Scheduling a Fixed Product Flexible Open Shop With Transportation Considerations

Open Access
Parra Forero, Carlos Javier
Graduate Program:
Industrial Engineering
Master of Science
Document Type:
Master Thesis
Date of Defense:
Committee Members:
  • Dr Jose Ventura, Thesis Advisor
  • Scheduling
  • PSO
  • Optimization
In the scheduling literature a lot of attention has been given to flow-shops and job-shops, since these problems usually have more constraints than open-shops. However, not only is the open-shop scheduling problem an NP-Complete problem for more than two machines, but is often encountered in several industrial applications. Additionally, due to the lack of constraints in open-shops, these problems have a much larger solution space. In this work, a Particle Swarm Optimization (PSO) heuristic is developed and implemented in order to solve a fixed product flexible open-shop with transportation considerations. That is, given a set of heterogeneous workers, a set of locations, and a set of tasks at each location, the methodology assigns the workers to the different tasks, and routes them through the different locations. All the workers begin and end their route at a depot or home location. This assignment and routing of the workers is done in such a way that a given performance measure is optimized; in this case, the goal is to minimize the makespan. The makespan is defined as the time period from the moment the first worker leaves, and the moment when the last worker returns. The travel times between locations are assumed to be non-trivial, and equal across workers. The proposed PSO approach was implemented on 10 sample problems and the results were compared to those obtained via a Mixed Integer Linear Program (MILP). The problems range from three to 10 workers, from two to five tasks per location and from four to 14 locations. The results show that the PSO could be potentially implemented to solve these types of problems. PSO was able to find a solution to the sample problems in a shorter time, than that required for the MILP to find the optimal. On average, the computational time was reduced by 60% when utilizing PSO; however, the quality of the solution can be further improved. The PSO heuristic achieved optimal results for five of the 10 problems, while the solution obtained for the remaining five problems was sub-optimal. It is clear that the problem size plays an important role on the behavior of PSO. For larger problems, the algorithm seems to be suffering from stagnation (early convergence). In the future, the performance of the algorithm can be improved by incorporating local search heuristics, as well as a better quality initial swarm. Additionally, some random movement of particles to prevent stagnation could be explored.