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

The open shop scheduling problem with a given sequence of jobs on one machine

Author

Listed:
  • Y.M. Shafransky
  • V.A. Strusevich

Abstract

The paper considers the open shop scheduling problem to minimize the make‐span, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not allowed, the problem is NP‐hard in the strong sense if the number of machines is variable, and is NP‐hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5/4 times the optimal value. We also show that the two‐machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 705–731, 1998

Suggested Citation

  • Y.M. Shafransky & V.A. Strusevich, 1998. "The open shop scheduling problem with a given sequence of jobs on one machine," Naval Research Logistics (NRL), John Wiley & Sons, vol. 45(7), pages 705-731, October.
    • Handle: RePEc:wly:navres:v:45:y:1998:i:7:p:705-731
    DOI: 10.1002/(SICI)1520-6750(199810)45:73.0.CO;2-F
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/(SICI)1520-6750(199810)45:73.0.CO;2-F
    Download Restriction: no
    File URL: https://libkey.io/10.1002/(SICI)1520-6750(199810)45:73.0.CO;2-F?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. V.A. Strusevich, 1997. "Shop scheduling problems under precedence constraints," Annals of Operations Research, Springer, vol. 69(0), pages 351-377, January.
    2. Clyde L. Monma, 1980. "Sequencing to Minimize the Maximum Job Cost," Operations Research, INFORMS, vol. 28(4), pages 942-951, August.
    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. Ting-Chun Lo & Bertrand M. T. Lin, 2021. "Relocation Scheduling in a Two-Machine Flow Shop with Resource Recycling Operations," Mathematics, MDPI, vol. 9(13), pages 1-35, June.
    2. Man-Ting Chao & Bertrand M. T. Lin, 2023. "Scheduling of Software Test to Minimize the Total Completion Time," Mathematics, MDPI, vol. 11(22), pages 1-17, November.
    3. A.A. Gladky & Y.M. Shafransky & V.A. Strusevich, 2004. "Flow Shop Scheduling Problems Under Machine–Dependent Precedence Constraints," Journal of Combinatorial Optimization, Springer, vol. 8(1), pages 13-28, March.
    4. T.C.E. Cheng & Svetlana A. Kravchenko & Bertrand M. T. Lin, 2019. "Server scheduling on parallel dedicated machines with fixed job sequences," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(4), pages 321-332, June.
    5. 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.
    6. F. Hwang & M. Kovalyov & B. Lin, 2014. "Scheduling for fabrication and assembly in a two-machine flowshop with a fixed job sequence," Annals of Operations Research, Springer, vol. 217(1), pages 263-279, June.
    7. Enrique Gerstl & Gur Mosheiov, 2023. "A note: maximizing the weighted number of Just-in-Time jobs for a given job sequence," Journal of Scheduling, Springer, vol. 26(4), pages 403-409, August.
    8. B. M. T. Lin & T. C. E. Cheng, 2011. "Scheduling with centralized and decentralized batching policies in concurrent open shops," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(1), pages 17-27, 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. A.A. Gladky & Y.M. Shafransky & V.A. Strusevich, 2004. "Flow Shop Scheduling Problems Under Machine–Dependent Precedence Constraints," Journal of Combinatorial Optimization, Springer, vol. 8(1), pages 13-28, March.
    2. Chen, Feng & Lee, Chung-Yee, 2009. "Minimizing the makespan in a two-machine cross-docking flow shop problem," European Journal of Operational Research, Elsevier, vol. 193(1), pages 59-72, February.
    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. Hans Kellerer & Vladimir Kotov & Franz Rendl & Gerhard J. Woeginger, 1998. "The Stock Size Problem," Operations Research, INFORMS, vol. 46(3-supplem), pages 1-12, June.
    5. Chung-Yee Lee & Ming Liu & Chengbin Chu, 2015. "Optimal Algorithm for the General Quay Crane Double-Cycling Problem," Transportation Science, INFORMS, vol. 49(4), pages 957-967, November.

    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:7:p:705-731. 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.