IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v45y1998i1p51-66.html
   My bibliography  Save this article

Openshop scheduling under linear resources constraints

Author

Listed:
  • I. Adiri
  • O. Hamberg

Abstract

Consider n jobs (J1, …, Jn), m working stations (M1, …, Mm) and λ linear resources (R1, …, Rλ). Job Ji consists of m operations (Oi1, …, Oim). Operation Oij requires Pk(i, j) units of resource Rk to be realized in an Mj. The availability of resource Rk and the ability of the working station Mh to consume resource Rk, vary over time. An operation involving more than one resource consumes them in constant proportions equal to those in which they are required. The order in which operations are realized is immaterial. We seek an allocation of the resources such that the schedule length is minimized. In this paper, polynomial algorithms are developed for several problems, while NP‐hardness is demonstrated for several others. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 51–66, 1998

Suggested Citation

  • I. Adiri & O. Hamberg, 1998. "Openshop scheduling under linear resources constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 45(1), pages 51-66, February.
    • Handle: RePEc:wly:navres:v:45:y:1998:i:1:p:51-66
    DOI: 10.1002/(SICI)1520-6750(199802)45:13.0.CO;2-K
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/(SICI)1520-6750(199802)45:13.0.CO;2-K
    Download Restriction: no
    File URL: https://libkey.io/10.1002/(SICI)1520-6750(199802)45:13.0.CO;2-K?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Slowinski, Roman, 1981. "Multiobjective network scheduling with efficient use of renewable and nonrenewable resources," European Journal of Operational Research, Elsevier, vol. 7(3), pages 265-273, July.
    2. Julius Surkis & Ali Dogramaci, 1988. "Minimizing the sum of weighted completion times of n‐independent jobs when resource availability varies over time: Performance of a simple priority rule," Naval Research Logistics (NRL), John Wiley & Sons, vol. 35(1), pages 35-47, February.
    3. Kenneth R. Baker & Henry L. W. Nuttle, 1980. "Sequencing independent jobs with a single resource," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 27(3), pages 499-510, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Paraskevopoulos, Dimitris C. & Laporte, Gilbert & Repoussis, Panagiotis P. & Tarantilis, Christos D., 2017. "Resource constrained routing and scheduling: Review and research prospects," European Journal of Operational Research, Elsevier, vol. 263(3), pages 737-754.
    2. Schirmer, Andreas, 1996. "New insights on the complexity of resource-constrained project scheduling: A case of single-mode scheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 390, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    3. Bahram Alidaee & Haibo Wang & R. Bryan Kethley & Frank Landram, 2019. "A unified view of parallel machine scheduling with interdependent processing rates," Journal of Scheduling, Springer, vol. 22(5), pages 499-515, October.
    4. Herroelen, Willy S. & Van Dommelen, Patrick & Demeulemeester, Erik L., 1997. "Project network models with discounted cash flows a guided tour through recent developments," European Journal of Operational Research, Elsevier, vol. 100(1), pages 97-121, July.
    5. T'kindt, V. & Billaut, J-C. & Proust, C., 2001. "Solving a bicriteria scheduling problem on unrelated parallel machines occurring in the glass bottle industry," European Journal of Operational Research, Elsevier, vol. 135(1), pages 42-49, November.
    6. Drexl, Andreas & Grünewald, Jürgen, 1989. "Nonpreemptive multi-mode resource-constrained project scheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 236, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    7. Schirmer, Andreas & Potzahr, Kathrin, 2001. "Lehrgangsplanung für die Ausbildung von Verkehrsflugzeugführern: Ergebnisse einer Studie bei Lufthansa Flight Training," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 538, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    8. Kolisch, Rainer & Sprecher, Arno, 1996. "PSPLIB - a project scheduling problem library," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 396, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    9. Tzafestas, Spyros & Triantafyllakis, Alekos, 1993. "Deterministic scheduling in computing and manufacturing systems: a survey of models and algorithms," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 35(5), pages 397-434.
    10. Van Peteghem, Vincent & Vanhoucke, Mario, 2014. "An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances," European Journal of Operational Research, Elsevier, vol. 235(1), pages 62-72.
    11. Schirmer, Andreas, 1996. "New insights on the complexity of resource-constrained project scheduling: Two cases of multi-mode scheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 391, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    12. Kolisch, Rainer & Sprecher, Arno & Drexl, Andreas, 1992. "Characterization and generation of a general class of resource-constrained project scheduling problems: Easy and hard instances," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 301, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    13. Laslo, Zohar & Golenko-Ginzburg, Dimitri & Keren, Baruch, 2008. "Optimal booking of machines in a virtual job-shop with stochastic processing times to minimize total machine rental and job tardiness costs," International Journal of Production Economics, Elsevier, vol. 111(2), pages 812-821, February.
    14. Sprecher, Arno & Drexl, Andreas, 1996. "Solving Multi-Mode Resource-Constrained Project Scheduling Problems by a Simple, General and Powerful Sequeacing Algorithm. Part I: Theory," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 385, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    15. Moukrim, Aziz & Quilliot, Alain & Toussaint, Hélène, 2015. "An effective branch-and-price algorithm for the Preemptive Resource Constrained Project Scheduling Problem based on minimal Interval Order Enumeration," European Journal of Operational Research, Elsevier, vol. 244(2), pages 360-368.
    16. J. F. Chen & W. E. Wilhelm, 1994. "Optimizing the allocation of components to kits in small‐lot, multiechelon assembly systems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 41(2), pages 229-256, March.
    17. Li, Wei & Nault, Barrie R. & Ye, Honghan, 2019. "Trade-off balancing in scheduling for flow shop production and perioperative processes," European Journal of Operational Research, Elsevier, vol. 273(3), pages 817-830.
    18. Norbis, Mario & MacGregor Smith, J., 1996. "An interactive decision support system for the resource Constrained Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 94(1), pages 54-65, October.
    19. Boctor, Fayez F., 1996. "A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes," European Journal of Operational Research, Elsevier, vol. 90(2), pages 349-361, April.
    20. Shewchuk, John P. & Chang, T. C., 1995. "Resource-constrained job scheduling with recyclable resources," European Journal of Operational Research, Elsevier, vol. 81(2), pages 364-375, March.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:45:y:1998:i:1:p:51-66. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.