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 N82d8d893f7644787bd70439cec833bbc
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 Ndf8db0f84a2045479cd717e87712971f
26 schema:name Formulation and Tabu Search Algorithm for the Resource Constrained Project Scheduling Problem
27 schema:pagination 557-588
28 schema:productId N6ebe708507d94265b98a8b8c3fc31f78
29 N8a433e3bb08a40258105becb2006d6ff
30 Ne1fdb6fcbbc64e9d8bac6f7f457e88e3
31 schema:publisher Nc5de51b732a745ce873ec1c3007b724e
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 N5be9be9c70c248e490bcbbc7c55942e2
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 N1e20ccbc01ff4ce1be8004078fc93d0b rdf:first sg:person.016640446116.30
42 rdf:rest N92f88f4221e94dbea6ed13874debc5f3
43 N5be9be9c70c248e490bcbbc7c55942e2 schema:name Springer Nature - SN SciGraph project
44 rdf:type schema:Organization
45 N6ebe708507d94265b98a8b8c3fc31f78 schema:name doi
46 schema:value 10.1007/978-1-4615-1507-4_25
47 rdf:type schema:PropertyValue
48 N82d8d893f7644787bd70439cec833bbc rdf:first sg:person.015726430545.16
49 rdf:rest N1e20ccbc01ff4ce1be8004078fc93d0b
50 N8a433e3bb08a40258105becb2006d6ff schema:name dimensions_id
51 schema:value pub.1022146852
52 rdf:type schema:PropertyValue
53 N92f88f4221e94dbea6ed13874debc5f3 rdf:first sg:person.016066470751.54
54 rdf:rest Nbac8d6179594416eb82c6eee3c2ac56e
55 Nbac8d6179594416eb82c6eee3c2ac56e rdf:first sg:person.014351674303.45
56 rdf:rest rdf:nil
57 Nc5de51b732a745ce873ec1c3007b724e schema:location Boston, MA
58 schema:name Springer US
59 rdf:type schema:Organisation
60 Ndf8db0f84a2045479cd717e87712971f schema:isbn 978-1-4613-5588-5
61 978-1-4615-1507-4
62 schema:name Essays and Surveys in Metaheuristics
63 rdf:type schema:Book
64 Ne1fdb6fcbbc64e9d8bac6f7f457e88e3 schema:name readcube_id
65 schema:value 69836870ed414795af2556f87b823ee2523412e79f65f19b3023fc077133d198
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)


...