Research Article
An Ant-Colony Algorithm to Transform Jobshops into Flowshops: A Case of Shortest-Common-Supersequence Stringology Problem
@INPROCEEDINGS{10.1007/978-3-642-32615-8_40, author={Suchithra Rajendran and Chandrasekharan Rajendran and Hans Ziegler}, title={An Ant-Colony Algorithm to Transform Jobshops into Flowshops: A Case of Shortest-Common-Supersequence Stringology Problem}, proceedings={6th International ICST Conference on Bio-Inspired Models of Network, Information, and Computing Systems}, proceedings_a={BIOADCOM}, year={2012}, month={10}, keywords={Jobshop Flowshop Shortest Common Supersequence Ant-colony algorithm}, doi={10.1007/978-3-642-32615-8_40} }- Suchithra Rajendran
Chandrasekharan Rajendran
Hans Ziegler
Year: 2012
An Ant-Colony Algorithm to Transform Jobshops into Flowshops: A Case of Shortest-Common-Supersequence Stringology Problem
BIOADCOM
Springer
DOI: 10.1007/978-3-642-32615-8_40
Abstract
In this work we address the problem of transforming a jobshop layout into a flowshop layout with the objective of minimizing the length of the resulting flowline. This problem is a special case of the well-known classical Shortest Common Supersequence (SCS) stringology problem. In view of the problem being NP-hard, an ant-colony algorithm, called PACO-SFR, is proposed. A new scheme of forming an initial supersequence of machines (i.e., flowline) is derived from a permutation of jobs, followed by the reduction in the length of the flowline by using a concatenation of forward reduction and inverse reduction techniques, machine elimination technique and finally an adjacent pair-wise interchange of machines in the flowline. The proposed ant-colony algorithm’s performance is relatively evaluated against the best known results from the existing methods by considering many benchmark jobshop scheduling problem instances.
