Complexity of late work minimization in flow shop systems and a particle swarm optimization algorithm for learning effect

- 3 machines flowshop late work minimization problem with common due date is NP-hard.
- A Heuristic based on particle swarm optimization method and learning effect.
- Experiments on the problem of flowshop with arbitrary number of machines.
- The heuristic is a reasonable solution, from performance and time-consumption views.

Late work minimization is one of the newer branches in the scheduling theory, with the goal of minimizing the total size of late parts of all jobs in the system. In this paper, we study the scheduling problem in flow shop, which finds many practical applications. First, we prove that the problem with three machines and a common due date is NP-hard in the strong sense. Then we extend this basic model, considering the problem with the arbitrary number of machines, various due dates and learning effect, and propose a particle swarm optimization algorithm (PSO). Computational experiments show that the PSO is an efficient method for solving the problem under consideration, both from algorithm-performance and time-consumption views.