Flow-shop sequencing using hybrid simulated annealing View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2004-06

AUTHORS

Andreas C. Nearchou

ABSTRACT

Simulated annealing (SA) heuristics have been successfully applied on a variety of complex optimization problems. This paper presents a new hybrid SA approach for the permutation flow-shop scheduling (FSS) problem. FSS is known to be NP-hard, and thus the right way to proceed is through the use of heuristics techniques. The proposed approach combines the characteristics of a canonical SA procedure together with features borrowed from the field of genetic algorithms (GAs), such as the use of a population of individuals and the use of a novel, non-standard recombination operator for generating solutions. The approach is easily implemented and performs near-optimal schedules in a rather short computation time. Experiments over multiple benchmarks test problems show that the developed approach has higher performance than that of other FSS meta-heuristic approaches, generating schedules of shorter makespans faster. The experiments include comparisons between the proposed hybrid model, a genetic algorithm, and two other standard simulated annealing approaches. The final solutions obtained by the method are within less than 1% in average from the optimal solutions obtained so far. More... »

PAGES

317-328

References to SciGraph publications

  • 1986-01. Convergence of an annealing algorithm in MATHEMATICAL PROGRAMMING
  • 1998. Inver-over operator for the TSP in PARALLEL PROBLEM SOLVING FROM NATURE — PPSN V
  • 1971-03. A Functional Heuristic Algorithm for the Flowshop Scheduling Problem in JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/b:jims.0000026570.03851.cc

    DOI

    http://dx.doi.org/10.1023/b:jims.0000026570.03851.cc

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1024659719


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Patras", 
              "id": "https://www.grid.ac/institutes/grid.11047.33", 
              "name": [
                "Department of Business Administration, University of Patras, 26 500, Rio, Patras, Greece"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Nearchou", 
            "givenName": "Andreas C.", 
            "id": "sg:person.011571005777.55", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011571005777.55"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0377-2217(93)e0235-p", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000191068"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0377-2217(93)90182-m", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002804663"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0377-2217(93)90182-m", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002804663"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0305-0483(83)90088-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005417958"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0305-0483(83)90088-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005417958"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0377-2217(90)90090-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013760542"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0377-2217(90)90090-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013760542"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/nav.3800010110", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014961200"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0305-0548(93)e0014-k", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016312562"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0305-0483(89)90059-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021103998"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0305-0483(89)90059-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021103998"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0377-2217(98)00308-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024715584"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1057/jors.1971.18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030092673", 
              "https://doi.org/10.1057/jors.1971.18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0305-0548(90)90001-n", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033571677"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0305-0548(90)90001-n", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033571677"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0377-2217(97)00136-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045701947"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0056922", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046722259", 
              "https://doi.org/10.1007/bfb0056922"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01582166", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049532067", 
              "https://doi.org/10.1007/bf01582166"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1126/science.220.4598.671", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062526985"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/mnsc.16.10.b630", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064716556"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/mnsc.23.11.1174", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064718754"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.13.3.400", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064726861"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/3006688", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1102672122"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004-06", 
        "datePublishedReg": "2004-06-01", 
        "description": "Simulated annealing (SA) heuristics have been successfully applied on a variety of complex optimization problems. This paper presents a new hybrid SA approach for the permutation flow-shop scheduling (FSS) problem. FSS is known to be NP-hard, and thus the right way to proceed is through the use of heuristics techniques. The proposed approach combines the characteristics of a canonical SA procedure together with features borrowed from the field of genetic algorithms (GAs), such as the use of a population of individuals and the use of a novel, non-standard recombination operator for generating solutions. The approach is easily implemented and performs near-optimal schedules in a rather short computation time. Experiments over multiple benchmarks test problems show that the developed approach has higher performance than that of other FSS meta-heuristic approaches, generating schedules of shorter makespans faster. The experiments include comparisons between the proposed hybrid model, a genetic algorithm, and two other standard simulated annealing approaches. The final solutions obtained by the method are within less than 1% in average from the optimal solutions obtained so far.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1023/b:jims.0000026570.03851.cc", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1043477", 
            "issn": [
              "0956-5515", 
              "1572-8145"
            ], 
            "name": "Journal of Intelligent Manufacturing", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "15"
          }
        ], 
        "name": "Flow-shop sequencing using hybrid simulated annealing", 
        "pagination": "317-328", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "757ac62066c2b5d22765d233e9f26eb394760de3c4b352006458d5a36b808ef8"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/b:jims.0000026570.03851.cc"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1024659719"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/b:jims.0000026570.03851.cc", 
          "https://app.dimensions.ai/details/publication/pub.1024659719"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T14:59", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8663_00000505.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1023%2FB%3AJIMS.0000026570.03851.cc"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1023/b:jims.0000026570.03851.cc'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1023/b:jims.0000026570.03851.cc'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/b:jims.0000026570.03851.cc'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/b:jims.0000026570.03851.cc'


     

    This table displays all metadata directly associated to this object as RDF triples.

    118 TRIPLES      21 PREDICATES      45 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/b:jims.0000026570.03851.cc schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author Naddbeae69bdf40e9814061b167007733
    4 schema:citation sg:pub.10.1007/bf01582166
    5 sg:pub.10.1007/bfb0056922
    6 sg:pub.10.1057/jors.1971.18
    7 https://doi.org/10.1002/nav.3800010110
    8 https://doi.org/10.1016/0305-0483(83)90088-9
    9 https://doi.org/10.1016/0305-0483(89)90059-5
    10 https://doi.org/10.1016/0305-0548(90)90001-n
    11 https://doi.org/10.1016/0305-0548(93)e0014-k
    12 https://doi.org/10.1016/0377-2217(90)90090-x
    13 https://doi.org/10.1016/0377-2217(93)90182-m
    14 https://doi.org/10.1016/0377-2217(93)e0235-p
    15 https://doi.org/10.1016/s0377-2217(97)00136-7
    16 https://doi.org/10.1016/s0377-2217(98)00308-7
    17 https://doi.org/10.1126/science.220.4598.671
    18 https://doi.org/10.1287/mnsc.16.10.b630
    19 https://doi.org/10.1287/mnsc.23.11.1174
    20 https://doi.org/10.1287/opre.13.3.400
    21 https://doi.org/10.2307/3006688
    22 schema:datePublished 2004-06
    23 schema:datePublishedReg 2004-06-01
    24 schema:description Simulated annealing (SA) heuristics have been successfully applied on a variety of complex optimization problems. This paper presents a new hybrid SA approach for the permutation flow-shop scheduling (FSS) problem. FSS is known to be NP-hard, and thus the right way to proceed is through the use of heuristics techniques. The proposed approach combines the characteristics of a canonical SA procedure together with features borrowed from the field of genetic algorithms (GAs), such as the use of a population of individuals and the use of a novel, non-standard recombination operator for generating solutions. The approach is easily implemented and performs near-optimal schedules in a rather short computation time. Experiments over multiple benchmarks test problems show that the developed approach has higher performance than that of other FSS meta-heuristic approaches, generating schedules of shorter makespans faster. The experiments include comparisons between the proposed hybrid model, a genetic algorithm, and two other standard simulated annealing approaches. The final solutions obtained by the method are within less than 1% in average from the optimal solutions obtained so far.
    25 schema:genre research_article
    26 schema:inLanguage en
    27 schema:isAccessibleForFree false
    28 schema:isPartOf N6838228b47f8457fbf97d1769d6e9bf8
    29 Nbdfe60d87f214d3f9998bcf8e4966e55
    30 sg:journal.1043477
    31 schema:name Flow-shop sequencing using hybrid simulated annealing
    32 schema:pagination 317-328
    33 schema:productId Nad319728c80d4d99afa11e7654326013
    34 Nc10273aec0c64b72a304cf5334c43ce9
    35 Nc2c3417a6e8c40c7a658976ad153a111
    36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024659719
    37 https://doi.org/10.1023/b:jims.0000026570.03851.cc
    38 schema:sdDatePublished 2019-04-10T14:59
    39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    40 schema:sdPublisher N88df0d1dac784850af76e0cfa1316825
    41 schema:url http://link.springer.com/10.1023%2FB%3AJIMS.0000026570.03851.cc
    42 sgo:license sg:explorer/license/
    43 sgo:sdDataset articles
    44 rdf:type schema:ScholarlyArticle
    45 N6838228b47f8457fbf97d1769d6e9bf8 schema:issueNumber 3
    46 rdf:type schema:PublicationIssue
    47 N88df0d1dac784850af76e0cfa1316825 schema:name Springer Nature - SN SciGraph project
    48 rdf:type schema:Organization
    49 Nad319728c80d4d99afa11e7654326013 schema:name doi
    50 schema:value 10.1023/b:jims.0000026570.03851.cc
    51 rdf:type schema:PropertyValue
    52 Naddbeae69bdf40e9814061b167007733 rdf:first sg:person.011571005777.55
    53 rdf:rest rdf:nil
    54 Nbdfe60d87f214d3f9998bcf8e4966e55 schema:volumeNumber 15
    55 rdf:type schema:PublicationVolume
    56 Nc10273aec0c64b72a304cf5334c43ce9 schema:name dimensions_id
    57 schema:value pub.1024659719
    58 rdf:type schema:PropertyValue
    59 Nc2c3417a6e8c40c7a658976ad153a111 schema:name readcube_id
    60 schema:value 757ac62066c2b5d22765d233e9f26eb394760de3c4b352006458d5a36b808ef8
    61 rdf:type schema:PropertyValue
    62 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Information and Computing Sciences
    64 rdf:type schema:DefinedTerm
    65 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Artificial Intelligence and Image Processing
    67 rdf:type schema:DefinedTerm
    68 sg:journal.1043477 schema:issn 0956-5515
    69 1572-8145
    70 schema:name Journal of Intelligent Manufacturing
    71 rdf:type schema:Periodical
    72 sg:person.011571005777.55 schema:affiliation https://www.grid.ac/institutes/grid.11047.33
    73 schema:familyName Nearchou
    74 schema:givenName Andreas C.
    75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011571005777.55
    76 rdf:type schema:Person
    77 sg:pub.10.1007/bf01582166 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049532067
    78 https://doi.org/10.1007/bf01582166
    79 rdf:type schema:CreativeWork
    80 sg:pub.10.1007/bfb0056922 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046722259
    81 https://doi.org/10.1007/bfb0056922
    82 rdf:type schema:CreativeWork
    83 sg:pub.10.1057/jors.1971.18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030092673
    84 https://doi.org/10.1057/jors.1971.18
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1002/nav.3800010110 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014961200
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1016/0305-0483(83)90088-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005417958
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1016/0305-0483(89)90059-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021103998
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1016/0305-0548(90)90001-n schema:sameAs https://app.dimensions.ai/details/publication/pub.1033571677
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1016/0305-0548(93)e0014-k schema:sameAs https://app.dimensions.ai/details/publication/pub.1016312562
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1016/0377-2217(90)90090-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1013760542
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1016/0377-2217(93)90182-m schema:sameAs https://app.dimensions.ai/details/publication/pub.1002804663
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1016/0377-2217(93)e0235-p schema:sameAs https://app.dimensions.ai/details/publication/pub.1000191068
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1016/s0377-2217(97)00136-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045701947
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1016/s0377-2217(98)00308-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024715584
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1126/science.220.4598.671 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062526985
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1287/mnsc.16.10.b630 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064716556
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1287/mnsc.23.11.1174 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064718754
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1287/opre.13.3.400 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064726861
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.2307/3006688 schema:sameAs https://app.dimensions.ai/details/publication/pub.1102672122
    115 rdf:type schema:CreativeWork
    116 https://www.grid.ac/institutes/grid.11047.33 schema:alternateName University of Patras
    117 schema:name Department of Business Administration, University of Patras, 26 500, Rio, Patras, Greece
    118 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...