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

Dual criteria preemptive open‐shop problems with minimum makespan

Author

Listed:
  • George Vairaktarakis
  • Sartaj Sahni

Abstract

In this article we present an algorithm for the minimum makespan preemptive open shop, which is superior to existing algorithms in both space and time requirements. We define the more complex generalized open shop and flexible open shop and address the minimum makespan problem on these shops. We show how we can use the algorithm for the minimum makespan open shop to achieve load balancing in simple and generalized open shops without increasing the complexity of the algorithm. Load balancing dictates that the number of busy machines in each period is as even as possible. We also consider preventive maintenance issues in the open shop, and makespan retains its minimum value. In particular we consider the scenario where a machine can be maintained during any period that it happens to be idle. Also we consider the case that a maintenance schedule is prespecified. We show that this problem can be solved via a linear programming formulation that can also take into account release times for the jobs and ready times for the machines. Faster algorithms are presented for open shops with three machines or less. © 1995 John Wiley & Sons, Inc.

Suggested Citation

  • George Vairaktarakis & Sartaj Sahni, 1995. "Dual criteria preemptive open‐shop problems with minimum makespan," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(1), pages 103-121, February.
    • Handle: RePEc:wly:navres:v:42:y:1995:i:1:p:103-121
    DOI: 10.1002/1520-6750(199502)42:13.0.CO;2-R
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(199502)42:13.0.CO;2-R
    Download Restriction: no
    File URL: https://libkey.io/10.1002/1520-6750(199502)42:13.0.CO;2-R?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. E. L. Lawler & J. K. Lenstra & A. H. G. Rinnooy Kan, 1981. "Minimizing Maximum Lateness in a Two-Machine Open Shop," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 153-158, February.
    2. Teofilo Gonzalez, 1982. "Unit Execution Time Shop Problems," Mathematics of Operations Research, INFORMS, vol. 7(1), pages 57-66, February.
    3. Yookun Cho & Sartaj Sahni, 1981. "Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops," Operations Research, INFORMS, vol. 29(3), pages 511-522, June.
    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. Ahmadian, Mohammad Mahdi & Khatami, Mostafa & Salehipour, Amir & Cheng, T.C.E., 2021. "Four decades of research on the open-shop scheduling problem to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 295(2), pages 399-426.
    2. M.A. Kubzin & V.A. Strusevich & J. Breit & G. Schmidt, 2006. "Polynomial‐time approximation schemes for two‐machine open shop scheduling with nonavailability constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(1), pages 16-23, 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. Ahmadian, Mohammad Mahdi & Khatami, Mostafa & Salehipour, Amir & Cheng, T.C.E., 2021. "Four decades of research on the open-shop scheduling problem to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 295(2), pages 399-426.
    2. Liaw, Ching-Fang, 2005. "Scheduling preemptive open shops to minimize total tardiness," European Journal of Operational Research, Elsevier, vol. 162(1), pages 173-183, April.
    3. Shakhlevich, Natalia V. & Sotskov, Yuri N. & Werner, Frank, 2000. "Complexity of mixed shop scheduling problems: A survey," European Journal of Operational Research, Elsevier, vol. 120(2), pages 343-351, January.
    4. Timkovsky, Vadim G., 2003. "Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity," European Journal of Operational Research, Elsevier, vol. 149(2), pages 355-376, September.
    5. Matta, Marie E. & Elmaghraby, Salah E., 2010. "Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop," European Journal of Operational Research, Elsevier, vol. 201(3), pages 720-728, March.
    6. Kravchenko, Svetlana A., 1998. "A polynomial algorithm for a two-machine no-wait job-shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 106(1), pages 101-107, April.
    7. 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.
    8. Hoogeveen, Han, 2005. "Multicriteria scheduling," European Journal of Operational Research, Elsevier, vol. 167(3), pages 592-623, December.
    9. Blazewicz, Jacek & Domschke, Wolfgang & Pesch, Erwin, 1996. "The job shop scheduling problem: Conventional and new solution techniques," European Journal of Operational Research, Elsevier, vol. 93(1), pages 1-33, August.
    10. Baptiste, Philippe, 2003. "On minimizing the weighted number of late jobs in unit execution time open-shops," European Journal of Operational Research, Elsevier, vol. 149(2), pages 344-354, September.
    11. Espelage, W. & Wanke, E., 2005. "A linear time approximation algorithm for movement minimization in conveyor flow shop processing," European Journal of Operational Research, Elsevier, vol. 160(2), pages 485-500, January.
    12. Sedeno-Noda, A. & Alcaide, D. & Gonzalez-Martin, C., 2006. "Network flow approaches to pre-emptive open-shop scheduling problems with time-windows," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1501-1518, November.
    13. Dvir Shabtay & Moshe Kaspi, 2006. "Minimizing the makespan in open‐shop scheduling problems with a convex resource consumption function," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(3), pages 204-216, April.
    14. Valls, Vicente & Angeles Perez, M. & Sacramento Quintanilla, M., 1998. "A tabu search approach to machine scheduling," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 277-300, April.
    15. Cheng, Jinliang & Steiner, George & Stephenson, Paul, 2001. "A computational study with a new algorithm for the three-machine permutation flow-shop problem with release times," European Journal of Operational Research, Elsevier, vol. 130(3), pages 559-575, May.
    16. Panwalkar, S.S. & Koulamas, Christos, 2014. "The two-machine no-wait general and proportionate open shop makespan problem," European Journal of Operational Research, Elsevier, vol. 238(2), pages 471-475.
    17. Hans Kellerer & Thomas Tautenhahn & Gerhard Woeginger, 1995. "Note: Open‐shop scheduling with release dates to minimize maximum lateness," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(1), pages 141-145, February.
    18. Sedeño-Noda, A. & de Pablo, D. Alcaide López & González-Martín, C., 2009. "A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows," European Journal of Operational Research, Elsevier, vol. 196(1), pages 140-154, July.
    19. Nicholas G. Hall & 'Maseka Lesaoana & Chris N. Potts, 2001. "Scheduling with Fixed Delivery Dates," Operations Research, INFORMS, vol. 49(1), pages 134-144, February.
    20. M.A. Kubzin & V.A. Strusevich & J. Breit & G. Schmidt, 2006. "Polynomial‐time approximation schemes for two‐machine open shop scheduling with nonavailability constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(1), pages 16-23, February.

    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:42:y:1995:i:1:p:103-121. 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.