|
|
 |
| |
|
|
|
An Exchange Local Search Heuristic based Scheme for Permutation Flow Shop Problems |
|
|
|
PP: 209-215 |
|
|
|
Author(s) |
|
|
|
Ruey-Maw Chen,
Fu-Ren Hsieh,
|
|
|
|
Abstract |
|
|
| In manufacturing organization, one of the mechanisms to minimize makespan (the total completion time) requires machines
and operations to be in accordance with a specific flow sequence, i.e., each production run has the same processing order. Determining
the specific flow sequence to minimize the makespan is the well-known scheduling problem named permutation flow-shop problem
(PFSP) which has been confirmed to be an NP problem. Hence, numerous researchers have devoted themselves to solve this problem
effectively. However, many studies suffer from high computation complexity. This work suggests a simple exchange local search
heuristic scheme with amended simulated annealing to efficiently solve PFSP. The simple exchange local search is adopted for
generating the solution (product run) to reduce excessive computation complexity.Meanwhile, an amended simulated annealing strategy
concerning relative energy change is applied to stable acceptance probability of the hill-climbing. Moreover, a threshold for relative
energy change is designed to prevent divergence. Restated, a simple, stable and low computation complexity scheme is proposed to
handle NP-complete PFSP. Experimental results illustrate that the proposed scheme provides an effective and efficient way to shorten
makespan as required in production lines. |
|
|
|
|
|
|
|
