An Exploration and Exploitation Search Control Scheme for Permutation Flow Shop Problem

The permutation flow shop problem (PFSP) has been studied by many researches and applied to plenty of applications. The PFSP has been confirmed to be an NP-complete permutation sequencing scheduling problem. Hence, many search schemes for finding near optima of PFSP were proposed. Insertion and exchange are two well used search schemes in finding solutions. Intrinsically, insertion scheme results in large range search (exploration), while exchange scheme corresponding to small range search (exploitation). To enhance the search efficiency by controlling exploration and exploitation abilities, an asymmetric sigmoid decline control in search pace is proposed. Restated, solution search based on designed control strategy starting from exploration towards exploitation is proposed. Meanwhile, a modified SA is included for avoiding trapping on local optimal solution, which the fitness deviation based acceptance criterion is suggested for avoiding acute acceptance probability turbulence. The experimental results demonstrate that the proposed scheme is effective and efficient when comparing with other state-of-the-art methods.