IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v199y2009i3p706-722.html
   My bibliography  Save this article

An MILP for scheduling problems in an FMS with one vehicle

Author

Listed:
  • Caumond, A.
  • Lacomme, P.
  • Moukrim, A.
  • Tchernev, N.

Abstract

This paper concerns the mathematical formulation and optimal solutions for the Flexible Manufacturing Systems Scheduling Problem (FMSSP) with one vehicle. This linear formulation differs from the previously published ones as it takes into account the maximum number of jobs allowed in the system, limited input/output buffer capacities, empty vehicle trips and no-move-ahead trips simultaneously. Our objective is to propose optimal solutions for small and medium-sized instances and to examine a number of commonly used assumptions and heuristics. Computational experiments are carried out on instances adapted from Bilge and Ulusoy [Bilge, Ü., Ulusoy, G., 1995. A time window approach to simultaneous scheduling of machines and material handling system in an FMS. Operations Research 43, 1058-1070] and the following heuristics are evaluated: FIFO (First In First Out) rules for input/output buffer management; and FIFO, SPT (Shortest Processing Time), STT (Shortest Travel Time) and MOQS (Maximum Outgoing Queue Size) rules concerning the vehicle. The consequences of classical assumptions are also studied: ignoring empty trips, ignoring no-move-ahead constraints, and ignoring vehicle-disjunction constraints. The numerical experiments provide a set of optimal solutions and allow to evaluate the performances of heuristic search schemes.

Suggested Citation

  • Caumond, A. & Lacomme, P. & Moukrim, A. & Tchernev, N., 2009. "An MILP for scheduling problems in an FMS with one vehicle," European Journal of Operational Research, Elsevier, vol. 199(3), pages 706-722, December.
    • Handle: RePEc:eee:ejores:v:199:y:2009:i:3:p:706-722
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00460-8
    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. Co, Christine G. & Tanchoco, J. M. A., 1991. "A review of research on AGVS vehicle management," Engineering Costs and Production Economics, Elsevier, vol. 21(1), pages 35-42, February.
    2. Ümit Bilge & Gündüz Ulusoy, 1995. "A Time Window Approach to Simultaneous Scheduling of Machines and Material Handling System in an FMS," Operations Research, INFORMS, vol. 43(6), pages 1058-1070, December.
    3. Liu, Jiyin & MacCarthy, B. L., 1997. "A global MILP model for FMS scheduling," European Journal of Operational Research, Elsevier, vol. 100(3), pages 441-453, August.
    4. Tharma Ganesharajah & Nicholas Hall & Chelliah Sriskandarajah, 1998. "Design and operational issues in AGV-served manufacturing systems," Annals of Operations Research, Springer, vol. 76(0), pages 109-154, January.
    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. Lacomme, Philippe & Larabi, Mohand & Tchernev, Nikolay, 2013. "Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles," International Journal of Production Economics, Elsevier, vol. 143(1), pages 24-34.
    2. Philippe Lacomme & Aziz Moukrim & Alain Quilliot & Marina Vinot, 2019. "Integration of routing into a resource-constrained project scheduling problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(4), pages 421-464, December.
    3. Sun, Yige & Chung, Sai-Ho & Wen, Xin & Ma, Hoi-Lam, 2021. "Novel robotic job-shop scheduling models with deadlock and robot movement considerations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    4. Topal, Erkan & Ramazan, Salih, 2010. "A new MIP model for mine equipment scheduling by minimizing maintenance cost," European Journal of Operational Research, Elsevier, vol. 207(2), pages 1065-1071, December.
    5. Marie-Laure Espinouse & Grzegorz Pawlak & Malgorzata Sterna, 2017. "Complexity of Scheduling Problem in Single-Machine Flexible Manufacturing System with Cyclic Transportation and Unlimited Buffers," Journal of Optimization Theory and Applications, Springer, vol. 173(3), pages 1042-1054, June.
    6. Arash Amirteimoori & Reza Kia, 2023. "Concurrent scheduling of jobs and AGVs in a flexible job shop system: a parallel hybrid PSO-GA meta-heuristic," Flexible Services and Manufacturing Journal, Springer, vol. 35(3), pages 727-753, September.
    7. Hosseini, Amir & Otto, Alena & Pesch, Erwin, 2024. "Scheduling in manufacturing with transportation: Classification and solution techniques," European Journal of Operational Research, Elsevier, vol. 315(3), pages 821-843.
    8. Savic, Aleksandar & Kratica, Jozef & Milanovic, Marija & Dugosija, Djordje, 2010. "A mixed integer linear programming formulation of the maximum betweenness problem," European Journal of Operational Research, Elsevier, vol. 206(3), pages 522-527, November.
    9. Olatunde T. Baruwa & Miquel A. Piera, 2016. "A coloured Petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4773-4792, August.

    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. Vis, Iris F.A., 2006. "Survey of research in the design and control of automated guided vehicle systems," European Journal of Operational Research, Elsevier, vol. 170(3), pages 677-709, May.
    2. Le-Anh, T. & de Koster, M.B.M., 2004. "A Review Of Design And Control Of Automated Guided Vehicle Systems," ERIM Report Series Research in Management ERS;2004-030-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    3. Hosseini, Amir & Otto, Alena & Pesch, Erwin, 2024. "Scheduling in manufacturing with transportation: Classification and solution techniques," European Journal of Operational Research, Elsevier, vol. 315(3), pages 821-843.
    4. Bish, Ebru K., 2003. "A multiple-crane-constrained scheduling problem in a container terminal," European Journal of Operational Research, Elsevier, vol. 144(1), pages 83-107, January.
    5. Kap Hwan Kim & Jong Wook Bae, 2004. "A Look-Ahead Dispatching Method for Automated Guided Vehicles in Automated Port Container Terminals," Transportation Science, INFORMS, vol. 38(2), pages 224-234, May.
    6. Le-Anh, Tuan & De Koster, M.B.M., 2006. "A review of design and control of automated guided vehicle systems," European Journal of Operational Research, Elsevier, vol. 171(1), pages 1-23, May.
    7. Hwi Kim, Sang & Hwang, Hark, 1999. "An adaptive dispatching algorithm for automated guided vehicles based on an evolutionary process," International Journal of Production Economics, Elsevier, vol. 60(1), pages 465-472, April.
    8. James T. Lin & Chun-Chih Chiu & Edward Huang & Hung-Ming Chen, 2018. "A Multi-Fidelity Model Approach for Simultaneous Scheduling of Machines and Vehicles in Flexible Manufacturing Systems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(01), pages 1-20, February.
    9. Chang, Yung-Chia & Lee, Chung-Yee, 2004. "Machine scheduling with job delivery coordination," European Journal of Operational Research, Elsevier, vol. 158(2), pages 470-487, October.
    10. Arash Amirteimoori & Reza Kia, 2023. "Concurrent scheduling of jobs and AGVs in a flexible job shop system: a parallel hybrid PSO-GA meta-heuristic," Flexible Services and Manufacturing Journal, Springer, vol. 35(3), pages 727-753, September.
    11. Mantel, Ronald J. & Landeweerd, Henri R. A., 1995. "Design and operational control of an AGV system," International Journal of Production Economics, Elsevier, vol. 41(1-3), pages 257-266, October.
    12. Yun, Lingxiang & Li, Lin & Ma, Shuaiyin, 2022. "Demand response for manufacturing systems considering the implications of fast-charging battery powered material handling equipment," Applied Energy, Elsevier, vol. 310(C).
    13. Kim, Kap Hwan, 1995. "Positioning of automated guided vehicles in a loop layout to minimize the mean vehicle response time," International Journal of Production Economics, Elsevier, vol. 39(3), pages 201-214, May.
    14. Chen, Lu & Langevin, André & Lu, Zhiqiang, 2013. "Integrated scheduling of crane handling and truck transportation in a maritime container terminal," European Journal of Operational Research, Elsevier, vol. 225(1), pages 142-152.
    15. James T. Lin & Chun-Chih Chiu & Yu-Hsiang Chang, 2019. "Simulation-based optimization approach for simultaneous scheduling of vehicles and machines with processing time uncertainty in FMS," Flexible Services and Manufacturing Journal, Springer, vol. 31(1), pages 104-141, March.
    16. Hurink, Johann & Knust, Sigrid, 2005. "Tabu search algorithms for job-shop problems with a single transport robot," European Journal of Operational Research, Elsevier, vol. 162(1), pages 99-111, April.
    17. Amogh Bhosekar & Sandra Ekşioğlu & Tuğçe Işık & Robert Allen, 2023. "A discrete event simulation model for coordinating inventory management and material handling in hospitals," Annals of Operations Research, Springer, vol. 320(2), pages 603-630, January.
    18. Hichem Kamoun & Nicholas G. Hall & Chelliah Sriskandarajah, 1999. "Scheduling in Robotic Cells: Heuristics and Cell Design," Operations Research, INFORMS, vol. 47(6), pages 821-835, December.
    19. Ilias Vlachos & Rodrigo Martinez Pascazzi & Miltiadis Ntotis & Konstantina Spanaki & Stella Despoudi & Panagiotis Repoussis, 2022. "Smart and flexible manufacturing systems using Autonomous Guided Vehicles (AGVs) and the Internet of Things (IoT)," Post-Print hal-03825237, HAL.
    20. Andy Ham, 2020. "Transfer-robot task scheduling in flexible job shop," Journal of Intelligent Manufacturing, Springer, vol. 31(7), pages 1783-1793, October.

    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:ejores:v:199:y:2009:i:3:p:706-722. 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/eor .

    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.