On linear lower bounds for the resource constrained project scheduling problem

被引：1
作者：
Carlier, J [1 ]
Néron, E
机构：
[1] Univ Technol Compiegne, CNRS, UMR 6599, Lab HeuDiaSyC, F-60260 Compiegne, France
[2] Univ Tours, Equipe Ordonnancement & Conduite, Lab Informat, F-37200 Tours, France
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2003年 / 149卷 / 02期
关键词：
resource constrained project scheduling; linear programming; lower bounds; redundant resources;
D O I：
10.1016/S0377-2217(02)00763-4
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
The aim of this paper is to propose efficient methods for solving the resource constrained project scheduling problem (RCPSP). These methods are based on makespan lower bounds, which linearly depend on the processing times of the activities. Linear lower bounds (LLB) can be obtained in different ways. The first application that we present is a general linear programming scheme for computing a makespan lower bound. The second application consists in associating redundant resources with LLB. Consequently we get new adjustments of release dates and tails of the project activities. These adjustments are tight for certain RCPSP instances, as shown by our computational results. (C) 2003 Published by Elsevier Science B.V.
引用
收藏
页码：314 / 324
页数：11
相关论文
共 50 条
  • [41] Comparison of mixed integer linear programming models for the resource-constrained project scheduling problem with consumption and production of resources
    Kone, Oumar
    Artigues, Christian
    Lopez, Pierre
    Mongeau, Marcel
    FLEXIBLE SERVICES AND MANUFACTURING JOURNAL, 2013, 25 (1-2) : 25 - 47
  • [42] An event-based reactive scheduling approach for the Resource Constrained Project Scheduling Problem with unreliable resources
    Chakrabortty, Ripon K.
    Rahman, Humyun Fuad
    Haque, Khan M. A.
    Paul, Sanjoy Kumar
    Ryan, Michael J.
    COMPUTERS & INDUSTRIAL ENGINEERING, 2021, 151
  • [43] On the strength of time-indexed formulations for the resource-constrained project scheduling problem
    Artigues, Christian
    OPERATIONS RESEARCH LETTERS, 2017, 45 (02) : 154 - 159
  • [44] Minimizing total weighted late work in the resource-constrained project scheduling problem
    Ranjbar, Mohammad
    Hosseinabadi, Saeed
    Abasian, Foroogh
    APPLIED MATHEMATICAL MODELLING, 2013, 37 (23) : 9776 - 9785
  • [45] Comparison of Heuristic Priority Rules in the Solution of the Resource-Constrained Project Scheduling Problem
    Turkakin, Osman Hurol
    Arditi, David
    Manisali, Ekrem
    SUSTAINABILITY, 2021, 13 (17)
  • [46] An Exact Procedure for the Resource-Constrained Weighted Earliness–Tardiness Project Scheduling Problem
    Mario Vanhoucke
    Erik Demeulemeester
    Willy Herroelen
    Annals of Operations Research, 2001, 102 : 179 - 196
  • [47] Meta-heuristic Techniques to Solve Resource-Constrained Project Scheduling Problem
    Roy, Bidisha
    Sen, Asim Kumar
    INTERNATIONAL CONFERENCE ON INNOVATIVE COMPUTING AND COMMUNICATIONS, VOL 2, 2019, 56 : 93 - 99
  • [48] NEW PSEUDO POLYNOMIAL ALGORITHMS FOR A PARTIAL RESOURCE-CONSTRAINED PROJECT SCHEDULING PROBLEM
    Wei, Hanying
    Su, Zhixiong
    Qi, Jianxun
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2023, 19 (11) : 8271 - 8298
  • [49] Approximability results for the resource-constrained project scheduling problem with a single type of resources
    Gafarov, Evgeny R.
    Lazarev, Alexander A.
    Werner, Frank
    ANNALS OF OPERATIONS RESEARCH, 2014, 213 (01) : 115 - 130
  • [50] A resource constrained project scheduling problem with discounted cash flows: A genetic algorithm approach
    Tasan, Seren Ozmehmet
    Gen, Mitsuo
    PROCEEDING OF THE SEVENTH INTERNATIONAL CONFERENCE ON INFORMATION AND MANAGEMENT SCIENCES, 2008, 7 : 632 - 638
12345