IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v41y1995i9p1417-1430.html
   My bibliography  Save this article

The Discrete Resource Allocation Problem in Flow Lines

Author

Listed:
  • Selcuk Karabati

    (Bilkent University, Management Department, Faculty of Business Administration, Bilkent, Ankara 06533, Turkey)

  • Panagiotis Kouvelis

    (Duke University, The Fuqua School of Business, Durham, North Carolina 27706)

  • Gang Yu

    (The University of Texas at Austin, Management Science and Information Systems Department, College of Business Administration CBA 5.202, Austin, Texas 78712)

Abstract

In this paper we address the discrete resource allocation problem in a deterministic flow line. We assume that the processing times are convex and nonincreasing in the amount of resources allocated to the machines. We consider the resource allocation problem for a fixed sequence of jobs for various performance criteria (makespan, weighted sum of completion times, cycle time for cyclic schedules), and develop a formulation of the problem as a convex program, where the number of constraints grows exponentially with the number of jobs and machines. We also present a generalization of the formulation for resource allocation problems in acyclic directed graphs. We demonstrate that the problem is NP-complete in the strong sense and present an effective solution procedure. The solution procedure is an implicit enumeration scheme where a surrogate relaxation of the formulation is used to generate upper and lower bounds on the optimal objective function value. Finally, we address the simultaneous scheduling and resource allocation problem, and we present an approximate and iterative solution procedure for the problem.

Suggested Citation

  • Selcuk Karabati & Panagiotis Kouvelis & Gang Yu, 1995. "The Discrete Resource Allocation Problem in Flow Lines," Management Science, INFORMS, vol. 41(9), pages 1417-1430, September.
    • Handle: RePEc:inm:ormnsc:v:41:y:1995:i:9:p:1417-1430
    DOI: 10.1287/mnsc.41.9.1417
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.41.9.1417
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.41.9.1417?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
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Selcuk Karabati & Panagiotis Kouvelis & Gang Yu, 2001. "A Min-Max-Sum Resource Allocation Problem and Its Applications," Operations Research, INFORMS, vol. 49(6), pages 913-922, December.

    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:inm:ormnsc:v:41:y:1995:i:9:p:1417-1430. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.