IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v112y2008i1p168-176.html
   My bibliography  Save this article

Permutation flowshop scheduling problems with time lags to minimize the weighted sum of machine completion times

Author

Listed:
  • Fondrevelle, J.
  • Oulamara, A.
  • Portmann, M.-C.

Abstract

In this article, we consider flowshop scheduling problems with minimal and maximal time lag constraints. Such constraints extend precedence constraints between operations in the jobs and may be used to model various industrial applications. The objective is to minimize a non-classical criterion based on the weighted sum of machine completion times. We show that it generalizes makespan and we derive several complexity results for two- and three-machine problems. An exact algorithm based on a branch-and-bound procedure is developed to solve the permutation flowshop problem with m machines.

Suggested Citation

  • Fondrevelle, J. & Oulamara, A. & Portmann, M.-C., 2008. "Permutation flowshop scheduling problems with time lags to minimize the weighted sum of machine completion times," International Journal of Production Economics, Elsevier, vol. 112(1), pages 168-176, March.
    • Handle: RePEc:eee:proeco:v:112:y:2008:i:1:p:168-176
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925-5273(07)00136-3
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Edward Ignall & Linus Schrage, 1965. "Application of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems," Operations Research, INFORMS, vol. 13(3), pages 400-412, June.
    2. P. C. Gilmore & R. E. Gomory, 1964. "Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem," Operations Research, INFORMS, vol. 12(5), pages 655-679, October.
    3. Heilmann, Roland, 2003. "A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags," European Journal of Operational Research, Elsevier, vol. 144(2), pages 348-365, January.
    4. L. G. Mitten, 1959. "Sequencing n Jobs on Two Machines with Arbitrary Time Lags," Management Science, INFORMS, vol. 5(3), pages 293-298, April.
    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. Nadjat Meziani & Ammar Oulamara & Mourad Boudhar, 2019. "Two-machine flowshop scheduling problem with coupled-operations," Annals of Operations Research, Springer, vol. 275(2), pages 511-530, April.
    2. E. Dhouib & J. Teghem & T. Loukil, 2018. "Non-permutation flowshop scheduling problem with minimal and maximal time lags: theoretical study and heuristic," Annals of Operations Research, Springer, vol. 267(1), pages 101-134, August.
    3. Ruiz-Torres, Alex J. & Ho, Johnny C. & Ablanedo-Rosas, José H., 2011. "Makespan and workstation utilization minimization in a flowshop with operations flexibility," Omega, Elsevier, vol. 39(3), pages 273-282, June.

    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. Khatami, Mostafa & Salehipour, Amir & Cheng, T.C.E., 2020. "Coupled task scheduling with exact delays: Literature review and models," European Journal of Operational Research, Elsevier, vol. 282(1), pages 19-39.
    2. Della Croce, F. & Narayan, V. & Tadei, R., 1996. "The two-machine total completion time flow shop problem," European Journal of Operational Research, Elsevier, vol. 90(2), pages 227-237, April.
    3. Sündüz Dağ, 2013. "An Application On Flowshop Scheduling," Alphanumeric Journal, Bahadir Fatih Yildirim, vol. 1(1), pages 47-56, December.
    4. Pan, Quan-Ke & Ruiz, Rubén, 2012. "Local search methods for the flowshop scheduling problem with flowtime minimization," European Journal of Operational Research, Elsevier, vol. 222(1), pages 31-43.
    5. Burkard, Rainer E., 2007. "Monge properties, discrete convexity and applications," European Journal of Operational Research, Elsevier, vol. 176(1), pages 1-14, January.
    6. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    7. B-J Joo & Y-D Kim, 2009. "A branch-and-bound algorithm for a two-machine flowshop scheduling problem with limited waiting time constraints," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(4), pages 572-582, April.
    8. Yen-Shing Tsai & Bertrand M. T. Lin, 2016. "Flow shop non-idle scheduling and resource-constrained scheduling," Annals of Operations Research, Springer, vol. 238(1), pages 577-585, March.
    9. Hartmann, Sönke & Briskorn, Dirk, 2010. "A survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 1-14, November.
    10. D Bai & L Tang, 2010. "New heuristics for flow shop problem to minimize makespan," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(6), pages 1032-1040, June.
    11. Dayal Madhukar & Verma, Sanjay, 2014. "Breadth-first and Best-first Exact Procedures for Regular Measures of the Multi-mode RCPSP," IIMA Working Papers WP2014-10-04, Indian Institute of Management Ahmedabad, Research and Publication Department.
    12. Waldherr, Stefan & Knust, Sigrid, 2017. "Decomposition algorithms for synchronous flow shop problems with additional resources and setup times," European Journal of Operational Research, Elsevier, vol. 259(3), pages 847-863.
    13. S Yanai & T Fujie, 2006. "A three-machine permutation flow-shop problem with minimum makespan on the second machine," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(4), pages 460-468, April.
    14. Lin, Shih-Wei & Ying, Kuo-Ching, 2013. "Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm," Omega, Elsevier, vol. 41(2), pages 383-389.
    15. Guangdong Wu, 2017. "A Multi-Objective Trade-Off Model in Sustainable Construction Projects," Sustainability, MDPI, vol. 9(11), pages 1-18, October.
    16. Lin, Shih-Wei & Ying, Kuo-Ching, 2016. "Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics," Omega, Elsevier, vol. 64(C), pages 115-125.
    17. Smutnicki, Czeslaw & Pempera, Jaroslaw & Bocewicz, Grzegorz & Banaszak, Zbigniew, 2022. "Cyclic flow-shop scheduling with no-wait constraints and missing operations," European Journal of Operational Research, Elsevier, vol. 302(1), pages 39-49.
    18. Dayal Madhukar & Verma, Sanjay, 2015. "Multi-processor Exact Procedures for Regular Measures of the Multi-mode RCPSP," IIMA Working Papers WP2015-03-25, Indian Institute of Management Ahmedabad, Research and Publication Department.
    19. 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.
    20. J. A. Hoogeveen & T. Kawaguchi, 1999. "Minimizing Total Completion Time in a Two-Machine Flowshop: Analysis of Special Cases," Mathematics of Operations Research, INFORMS, vol. 24(4), pages 887-910, 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:eee:proeco:v:112:y:2008:i:1:p:168-176. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/ijpe .

    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.