IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v46y1998i5p729-741.html
   My bibliography  Save this article

Parallel Machine Scheduling, Linear Programming, and Parameter List Scheduling Heuristics

Author

Listed:
  • Lap Mui Ann Chan

    (University of Toronto, Ontario, Canada)

  • Ana Muriel

    (University of Michigan, Ann Arbor, Michigan)

  • David Simchi-Levi

    (Northwestern University, Chicago, Illinois)

Abstract

In this paper we consider a class of parallel machine scheduling problems and their associated set-partitioning formulations. We show that the tightness of the linear programming relaxation of these formulations is directly related to the performance of a class of heuristics called parameter list scheduling heuristics. This makes it possible to characterize the worst possible gap between optimal solutions for the scheduling problems and the corresponding linear programming relaxations. In the case of the classical parallel machine weighted completion time model we also show that the solution to the linear programming relaxation of the set-partitioning formulation is asymptotically optimal under mild assumptions on the distribution of job weights and processing times. Finally, we extend most of the results to the time-discretized formulation of machine scheduling problems.

Suggested Citation

  • Lap Mui Ann Chan & Ana Muriel & David Simchi-Levi, 1998. "Parallel Machine Scheduling, Linear Programming, and Parameter List Scheduling Heuristics," Operations Research, INFORMS, vol. 46(5), pages 729-741, October.
    • Handle: RePEc:inm:oropre:v:46:y:1998:i:5:p:729-741
    DOI: 10.1287/opre.46.5.729
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.46.5.729
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.46.5.729?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. Julien Bramel & David Simchi-Levi, 1997. "On the Effectiveness of Set Covering Formulations for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 45(2), pages 295-301, April.
    2. SOUSA, Jorge P. & WOLSEY, Laurence A., 1992. "A time indexed formulation of non-preemptive single machine scheduling problems," LIDAM Reprints CORE 984, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Jonathan F. Bard & Siwate Rojanasoonthon, 2006. "A branch‐and‐price algorithm for parallel machine scheduling with time windows and job priorities," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(1), pages 24-44, February.
    2. J. G. Dai & Gideon Weiss, 2002. "A Fluid Heuristic for Minimizing Makespan in Job Shops," Operations Research, INFORMS, vol. 50(4), pages 692-707, August.
    3. Chung‐Yee Lee & Zhi‐Long Chen, 2000. "Scheduling jobs and maintenance activities on parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(2), pages 145-165, March.
    4. Marjan van den Akker & Han Hoogeveen & Steef van de Velde, 2002. "Combining Column Generation and Lagrangean Relaxation to Solve a Single-Machine Common Due Date Problem," INFORMS Journal on Computing, INFORMS, vol. 14(1), pages 37-51, February.

    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. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    2. Baptiste, Philippe & Sadykov, Ruslan, 2010. "Time-indexed formulations for scheduling chains on a single machine: An application to airborne radars," European Journal of Operational Research, Elsevier, vol. 203(2), pages 476-483, June.
    3. Abdessamad Ait El Cadi & Omar Souissi & Rabie Ben Atitallah & Nicolas Belanger & Abdelhakim Artiba, 2018. "Mathematical programming models for scheduling in a CPU/FPGA architecture with heterogeneous communication delays," Journal of Intelligent Manufacturing, Springer, vol. 29(3), pages 629-640, March.
    4. Liu, Fuh-Hwa Franklin & Shen, Sheng-Yuan, 1999. "A route-neighborhood-based metaheuristic for vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 118(3), pages 485-504, November.
    5. Sanjeev Swami & Jehoshua Eliashberg & Charles B. Weinberg, 1999. "SilverScreener: A Modeling Approach to Movie Screens Management," Marketing Science, INFORMS, vol. 18(3), pages 352-372.
    6. Balasubramanian, Hari & Fowler, John & Keha, Ahmet & Pfund, Michele, 2009. "Scheduling interfering job sets on parallel machines," European Journal of Operational Research, Elsevier, vol. 199(1), pages 55-67, November.
    7. Artur Alves Pessoa & Teobaldo Bulhões & Vitor Nesello & Anand Subramanian, 2022. "Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1512-1530, May.
    8. Song, Jiongjiong & Regan, Amelia, 2005. "Approximation algorithms for the bid construction problem in combinatorial auctions for the procurement of freight transportation contracts," Transportation Research Part B: Methodological, Elsevier, vol. 39(10), pages 914-933, December.
    9. Cochran, Jeffery K. & Marquez Uribe, Alberto, 2005. "A set covering formulation for agile capacity planning within supply chains," International Journal of Production Economics, Elsevier, vol. 95(2), pages 139-149, February.
    10. Averbakh, Igor & Pereira, Jordi, 2015. "Network construction problems with due dates," European Journal of Operational Research, Elsevier, vol. 244(3), pages 715-729.
    11. Victor Reyes & Ignacio Araya, 2021. "A GRASP-based scheme for the set covering problem," Operational Research, Springer, vol. 21(4), pages 2391-2408, December.
    12. Francis Sourd, 2009. "New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 167-175, February.
    13. Pasquale Avella & Maurizio Boccia & Bernardo D’Auria, 2005. "Near-Optimal Solutions of Large-Scale Single-Machine Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 17(2), pages 183-191, May.
    14. Klamroth, Kathrin & Wiecek, Margaret M., 2001. "A time-dependent multiple criteria single-machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 135(1), pages 17-26, November.
    15. Nizar Hachemi & Issmail Hallaoui & Michel Gendreau & Louis-Martin Rousseau, 2015. "Flow-based integer linear programs to solve the weekly log-truck scheduling problem," Annals of Operations Research, Springer, vol. 232(1), pages 87-97, September.
    16. Kelly Poldi & Silvio Araujo, 2016. "Mathematical models and a heuristic method for the multiperiod one-dimensional cutting stock problem," Annals of Operations Research, Springer, vol. 238(1), pages 497-520, March.
    17. Zhang, Hanxiao & Li, Yan-Fu, 2022. "Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers," European Journal of Operational Research, Elsevier, vol. 299(1), pages 183-194.
    18. L Tansini & O Viera, 2006. "New measures of proximity for the assignment algorithms in the MDVRPTW," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(3), pages 241-249, March.
    19. Wolsey, Laurence A., 1997. "MIP modelling of changeovers in production planning and scheduling problems," European Journal of Operational Research, Elsevier, vol. 99(1), pages 154-165, May.
    20. Irnich, Stefan, 2000. "A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles," European Journal of Operational Research, Elsevier, vol. 122(2), pages 310-328, April.

    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:oropre:v:46:y:1998:i:5:p:729-741. 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: 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.