6th International ICST Conference on Bio-Inspired Models of Network, Information, and Computing Systems

Research Article

An Ant-Colony Algorithm to Transform Jobshops into Flowshops: A Case of Shortest-Common-Supersequence Stringology Problem

Download
458 downloads
  • @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
Suchithra Rajendran1,*, Chandrasekharan Rajendran2,*, Hans Ziegler3,*
  • 1: Guindy, Anna University
  • 2: Indian Institute of Technology Madras
  • 3: University of Passau
*Contact email: snowy_410@yahoo.co.in, craj@iitm.ac.in, ziegler@uni-passau.de

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.