Formulation and Tabu Search Algorithm for the Resource Constrained Project Scheduling Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002

AUTHORS

Celso C. Ribeiro , Pierre Hansen , Koji Nonobe , Toshihide Ibaraki

ABSTRACT

The resource constrained project scheduling problem (RCPSP) can formulate many scheduling problems including jobshop and flowshop scheduling problems. In this paper, we extend the definition of RCPSP further so that various complicated constraints and objective functions arising in practice can be handled; for example, each activity can be processed in one of the selectable modes, the available amounts of renewable resources may vary depending on the periods, setup activities can be dealt with, and complex objective functions can be handled. Then, we develop a tabu search based heuristic algorithm, which contains elaborations in representing solutions and in constructing neighborhood. Our code was tested for many benchmarks of RCPSP, and also for some problems from real applications. For a number of RCPSP instances, we found better solutions than the best ones found so far. These computational results indicate the effectiveness and usefulness of our approach. More... »

PAGES

557-588

References to SciGraph publications

Book

TITLE

Essays and Surveys in Metaheuristics

ISBN

978-1-4613-5588-5
978-1-4615-1507-4

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-1-4615-1507-4_25

DOI

http://dx.doi.org/10.1007/978-1-4615-1507-4_25

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "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": [
      {
        "familyName": "Ribeiro", 
        "givenName": "Celso C.", 
        "id": "sg:person.015726430545.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015726430545.16"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Hansen", 
        "givenName": "Pierre", 
        "id": "sg:person.016640446116.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016640446116.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Kyoto University", 
          "id": "https://www.grid.ac/institutes/grid.258799.8", 
          "name": [
            "Department of Applied Mathematics and Physics Graduate School of Informatics, Kyoto University, Kyoto\u00a0606\u20138501, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nonobe", 
        "givenName": "Koji", 
        "id": "sg:person.016066470751.54", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016066470751.54"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Kyoto University", 
          "id": "https://www.grid.ac/institutes/grid.258799.8", 
          "name": [
            "Department of Applied Mathematics and Physics Graduate School of Informatics, Kyoto University, Kyoto\u00a0606\u20138501, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ibaraki", 
        "givenName": "Toshihide", 
        "id": "sg:person.014351674303.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014351674303.45"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0377-2217(98)80001-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015811140"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0377-2217(93)e0294-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022690625"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(96)00170-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023235531"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/1520-6750(199308)40:5<665::aid-nav3220400509>3.0.co;2-j", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025285712"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/1520-6750(199106)38:3<315::aid-nav3220380304>3.0.co;2-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026577347"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(96)00180-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027989003"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(97)00294-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030069058"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1009673512884", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030334677", 
          "https://doi.org/10.1023/a:1009673512884"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(98)00204-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033604652"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/(sici)1520-6750(199810)45:7<733::aid-nav5>3.0.co;2-c", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047848190"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0377-2217(95)00357-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049263655"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0305-0548(97)00055-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051503044"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0377-2217(95)00362-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1054560463"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/ijoc.1.3.190", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064706391"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/mnsc.30.7.854", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064719916"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2002", 
    "datePublishedReg": "2002-01-01", 
    "description": "The resource constrained project scheduling problem (RCPSP) can formulate many scheduling problems including jobshop and flowshop scheduling problems. In this paper, we extend the definition of RCPSP further so that various complicated constraints and objective functions arising in practice can be handled; for example, each activity can be processed in one of the selectable modes, the available amounts of renewable resources may vary depending on the periods, setup activities can be dealt with, and complex objective functions can be handled. Then, we develop a tabu search based heuristic algorithm, which contains elaborations in representing solutions and in constructing neighborhood. Our code was tested for many benchmarks of RCPSP, and also for some problems from real applications. For a number of RCPSP instances, we found better solutions than the best ones found so far. These computational results indicate the effectiveness and usefulness of our approach.", 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-1-4615-1507-4_25", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-1-4613-5588-5", 
        "978-1-4615-1507-4"
      ], 
      "name": "Essays and Surveys in Metaheuristics", 
      "type": "Book"
    }, 
    "name": "Formulation and Tabu Search Algorithm for the Resource Constrained Project Scheduling Problem", 
    "pagination": "557-588", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-1-4615-1507-4_25"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "69836870ed414795af2556f87b823ee2523412e79f65f19b3023fc077133d198"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022146852"
        ]
      }
    ], 
    "publisher": {
      "location": "Boston, MA", 
      "name": "Springer US", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-1-4615-1507-4_25", 
      "https://app.dimensions.ai/details/publication/pub.1022146852"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T00:48", 
    "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_8700_00000256.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-1-4615-1507-4_25"
  }
]
 

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.1007/978-1-4615-1507-4_25'

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.1007/978-1-4615-1507-4_25'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-1-4615-1507-4_25'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-1-4615-1507-4_25'


 

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

124 TRIPLES      22 PREDICATES      41 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-1-4615-1507-4_25 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N31657670a74f45639f327923fba67fee
4 schema:citation sg:pub.10.1023/a:1009673512884
5 https://doi.org/10.1002/(sici)1520-6750(199810)45:7<733::aid-nav5>3.0.co;2-c
6 https://doi.org/10.1002/1520-6750(199106)38:3<315::aid-nav3220380304>3.0.co;2-7
7 https://doi.org/10.1002/1520-6750(199308)40:5<665::aid-nav3220400509>3.0.co;2-j
8 https://doi.org/10.1016/0377-2217(93)e0294-8
9 https://doi.org/10.1016/0377-2217(95)00357-6
10 https://doi.org/10.1016/0377-2217(95)00362-2
11 https://doi.org/10.1016/s0305-0548(97)00055-5
12 https://doi.org/10.1016/s0377-2217(96)00170-1
13 https://doi.org/10.1016/s0377-2217(96)00180-4
14 https://doi.org/10.1016/s0377-2217(97)00294-4
15 https://doi.org/10.1016/s0377-2217(98)00204-5
16 https://doi.org/10.1016/s0377-2217(98)80001-5
17 https://doi.org/10.1287/ijoc.1.3.190
18 https://doi.org/10.1287/mnsc.30.7.854
19 schema:datePublished 2002
20 schema:datePublishedReg 2002-01-01
21 schema:description The resource constrained project scheduling problem (RCPSP) can formulate many scheduling problems including jobshop and flowshop scheduling problems. In this paper, we extend the definition of RCPSP further so that various complicated constraints and objective functions arising in practice can be handled; for example, each activity can be processed in one of the selectable modes, the available amounts of renewable resources may vary depending on the periods, setup activities can be dealt with, and complex objective functions can be handled. Then, we develop a tabu search based heuristic algorithm, which contains elaborations in representing solutions and in constructing neighborhood. Our code was tested for many benchmarks of RCPSP, and also for some problems from real applications. For a number of RCPSP instances, we found better solutions than the best ones found so far. These computational results indicate the effectiveness and usefulness of our approach.
22 schema:genre chapter
23 schema:inLanguage en
24 schema:isAccessibleForFree false
25 schema:isPartOf N3c3165a7eb8144ab8af3d57e7706ab6d
26 schema:name Formulation and Tabu Search Algorithm for the Resource Constrained Project Scheduling Problem
27 schema:pagination 557-588
28 schema:productId N0b4968474562465cb6ca5af56e2fa0e1
29 N6e795a1269054128860dd52efb91b619
30 Ne3ee51beec264ea4b1075964a1867a54
31 schema:publisher N485132c6697842c4aa7e8867a88a04f2
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022146852
33 https://doi.org/10.1007/978-1-4615-1507-4_25
34 schema:sdDatePublished 2019-04-16T00:48
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher Naf5299aba0fb418280183ab31847a763
37 schema:url http://link.springer.com/10.1007/978-1-4615-1507-4_25
38 sgo:license sg:explorer/license/
39 sgo:sdDataset chapters
40 rdf:type schema:Chapter
41 N0b4968474562465cb6ca5af56e2fa0e1 schema:name doi
42 schema:value 10.1007/978-1-4615-1507-4_25
43 rdf:type schema:PropertyValue
44 N10c6b67be9914034810ca925d3c12acd rdf:first sg:person.014351674303.45
45 rdf:rest rdf:nil
46 N31657670a74f45639f327923fba67fee rdf:first sg:person.015726430545.16
47 rdf:rest Ne2612b817afe4f94a9e73d1f4a22e956
48 N3c3165a7eb8144ab8af3d57e7706ab6d schema:isbn 978-1-4613-5588-5
49 978-1-4615-1507-4
50 schema:name Essays and Surveys in Metaheuristics
51 rdf:type schema:Book
52 N485132c6697842c4aa7e8867a88a04f2 schema:location Boston, MA
53 schema:name Springer US
54 rdf:type schema:Organisation
55 N55bbc7581c8c414ca14694d43eca7b87 rdf:first sg:person.016066470751.54
56 rdf:rest N10c6b67be9914034810ca925d3c12acd
57 N6e795a1269054128860dd52efb91b619 schema:name readcube_id
58 schema:value 69836870ed414795af2556f87b823ee2523412e79f65f19b3023fc077133d198
59 rdf:type schema:PropertyValue
60 Naf5299aba0fb418280183ab31847a763 schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 Ne2612b817afe4f94a9e73d1f4a22e956 rdf:first sg:person.016640446116.30
63 rdf:rest N55bbc7581c8c414ca14694d43eca7b87
64 Ne3ee51beec264ea4b1075964a1867a54 schema:name dimensions_id
65 schema:value pub.1022146852
66 rdf:type schema:PropertyValue
67 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
68 schema:name Information and Computing Sciences
69 rdf:type schema:DefinedTerm
70 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
71 schema:name Computation Theory and Mathematics
72 rdf:type schema:DefinedTerm
73 sg:person.014351674303.45 schema:affiliation https://www.grid.ac/institutes/grid.258799.8
74 schema:familyName Ibaraki
75 schema:givenName Toshihide
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014351674303.45
77 rdf:type schema:Person
78 sg:person.015726430545.16 schema:familyName Ribeiro
79 schema:givenName Celso C.
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015726430545.16
81 rdf:type schema:Person
82 sg:person.016066470751.54 schema:affiliation https://www.grid.ac/institutes/grid.258799.8
83 schema:familyName Nonobe
84 schema:givenName Koji
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016066470751.54
86 rdf:type schema:Person
87 sg:person.016640446116.30 schema:familyName Hansen
88 schema:givenName Pierre
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016640446116.30
90 rdf:type schema:Person
91 sg:pub.10.1023/a:1009673512884 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030334677
92 https://doi.org/10.1023/a:1009673512884
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1002/(sici)1520-6750(199810)45:7<733::aid-nav5>3.0.co;2-c schema:sameAs https://app.dimensions.ai/details/publication/pub.1047848190
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1002/1520-6750(199106)38:3<315::aid-nav3220380304>3.0.co;2-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026577347
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1002/1520-6750(199308)40:5<665::aid-nav3220400509>3.0.co;2-j schema:sameAs https://app.dimensions.ai/details/publication/pub.1025285712
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1016/0377-2217(93)e0294-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022690625
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1016/0377-2217(95)00357-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049263655
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1016/0377-2217(95)00362-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1054560463
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/s0305-0548(97)00055-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051503044
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1016/s0377-2217(96)00170-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023235531
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/s0377-2217(96)00180-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027989003
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/s0377-2217(97)00294-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030069058
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/s0377-2217(98)00204-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033604652
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1016/s0377-2217(98)80001-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015811140
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1287/ijoc.1.3.190 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064706391
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1287/mnsc.30.7.854 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064719916
121 rdf:type schema:CreativeWork
122 https://www.grid.ac/institutes/grid.258799.8 schema:alternateName Kyoto University
123 schema:name Department of Applied Mathematics and Physics Graduate School of Informatics, Kyoto University, Kyoto 606–8501, Japan
124 rdf:type schema:Organization
 




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


...