A Molecular Algorithm for an Operation-based Job Shop Scheduling Problem

作者：Molaei Somayeh; Vahdani Behnam; Molaei Shahram

来源：Arabian Journal for Science and Engineering, 2013, 38(11): 2993-3003.

DOI：10.1007/s13369-012-0458-0

• DNA computing
• Intermediate time
• NP-hard
• Permutation
• Hamiltonian path

This paper proposes a molecular algorithm for a job shop problem based on intermediate time consumed between operations of jobs. This problem is an NP-complete problem in a silicon-based computation environment. Thus, using any parallel algorithm for solving this problem can be useful. In this paper, enormous parallelism power of molecular computation is used. In addition, intermediate consumed time between operations is considered. Our solution consists of specifying one direction of conjunctive edges between each pair of operations using both mask and coloring techniques. Based on the resulted directions in a graph, all the valid schedules are found and, finally, the best one is selected according to the consumed time of all operations. The proposed molecular algorithm performs in the complexity of O(max (n,m)). The effectiveness of this algorithm is verified by a computational simulation.

• 出版日期2013-11