Header menu link for other important links
X
An ant-colony algorithm to transform jobshops into flowshops: A case of shortest-common-supersequence stringology problem
Published in
2012
Volume: 87 LNICST
   
Pages: 413 - 424
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. © 2012 ICST Institute for Computer Science, Social Informatics and Telecommunications Engineering.
About the journal
JournalLecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering
ISSN18678211
Open AccessNo
Concepts (14)
  •  related image
    ANT-COLONY ALGORITHM
  •  related image
    ELIMINATION TECHNIQUES
  •  related image
    FLOW-SHOPS
  •  related image
    Job shop scheduling problems
  •  related image
    Job-shop
  •  related image
    JOBSHOP LAYOUT
  •  related image
    Np-hard
  •  related image
    REDUCTION TECHNIQUES
  •  related image
    SHORTEST COMMON SUPERSEQUENCE
  •  related image
    STRINGOLOGY
  •  related image
    SUPERSEQUENCE
  •  related image
    Benchmarking
  •  related image
    FLOWLINES
  •  related image
    Algorithms