IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v206y2013i1p311-33910.1007-s10479-012-1256-5.html
   My bibliography  Save this article

Formulating and solving a multi-mode resource-collaboration and constrained scheduling problem (MRCCSP)

Author

Listed:
  • Gaby Pinto
  • Yariv Ben-Dov
  • Gad Rabinowitz

Abstract

The main motivation of this study is to provide, for the first time, a formulation and solution for a class of production scheduling problems (as in cluster tools) characterized mainly by resource collaboration to perform an operation and while allowing batches and considering alternative production methods. We develop a formulation for the new problem and term it a multiple mode per operation, resource collaboration, and constrained scheduling problem (MRCCSP). Some of the important new characteristics we consider are: multiple products (families); multiple orders (jobs) per family; precedence restrictions among the operations that constitute a job; alternative modes for the performance of an operation (each of which needs a set of collaborating resources) may be defined; complementary and exclusive restrictions between operation-modes; batch production is allowed; and setup times may depend on sequence and batch-size. The objective of the MRCCSP is to minimize makespan. We formulate the MRCCSP as a mixed integer linear programming model, and acknowledging the considerable size of the monolithic formulation required, we prescribe a specific method to achieve size reduction. Finally, a customized branch and bound algorithm for optimally solving this problem is proposed and examined experimentally. Copyright Springer Science+Business Media New York 2013

Suggested Citation

  • Gaby Pinto & Yariv Ben-Dov & Gad Rabinowitz, 2013. "Formulating and solving a multi-mode resource-collaboration and constrained scheduling problem (MRCCSP)," Annals of Operations Research, Springer, vol. 206(1), pages 311-339, July.
    • Handle: RePEc:spr:annopr:v:206:y:2013:i:1:p:311-339:10.1007/s10479-012-1256-5
    DOI: 10.1007/s10479-012-1256-5
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-012-1256-5
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-012-1256-5?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
    ---><---

    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. Sawik, Tadeusz, 2004. "Loading and scheduling of a flexible assembly system by mixed integer programming," European Journal of Operational Research, Elsevier, vol. 154(1), pages 1-19, April.
    2. Graves, Stephen C., 1983. "Scheduling of re-entrant flow shops," Working papers 1438-83., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    3. Ulrich Dorndorf & Erwin Pesch & Toàn Phan-Huy, 2000. "A Time-Oriented Branch-and-Bound Algorithm for Resource-Constrained Project Scheduling with Generalised Precedence Constraints," Management Science, INFORMS, vol. 46(10), pages 1365-1384, October.
    4. Brucker, Peter & Knust, Sigrid & Schoo, Arno & Thiele, Olaf, 1998. "A branch and bound algorithm for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 107(2), pages 272-288, June.
    5. Samaddar, Subhashish & Rabinowitz, Gad & Zhang, Guoqiang Peter, 2005. "An experimental analysis of solution performance in a resource sharing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 165(1), pages 139-156, August.
    6. Brucker, Peter & Drexl, Andreas & Mohring, Rolf & Neumann, Klaus & Pesch, Erwin, 1999. "Resource-constrained project scheduling: Notation, classification, models, and methods," European Journal of Operational Research, Elsevier, vol. 112(1), pages 3-41, January.
    7. Weglarz, Jan & Józefowska, Joanna & Mika, Marek & Waligóra, Grzegorz, 2011. "Project scheduling with finite or infinite number of activity processing modes - A survey," European Journal of Operational Research, Elsevier, vol. 208(3), pages 177-205, February.
    8. Potts, Chris N. & Kovalyov, Mikhail Y., 2000. "Scheduling with batching: A review," European Journal of Operational Research, Elsevier, vol. 120(2), pages 228-249, January.
    9. Shih-Wei Lin & Zne-Jung Lee & Kuo-Ching Ying & Rong-Ho Lin, 2011. "Meta-heuristic algorithms for wafer sorting scheduling problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(1), pages 165-174, January.
    10. Das, Sidhartha R. & Canel, Cem, 2005. "An algorithm for scheduling batches of parts in a multi-cell flexible manufacturing system," International Journal of Production Economics, Elsevier, vol. 97(3), pages 247-262, September.
    11. Riane, F. & Artiba, A. & Iassinovski, S., 2001. "An integrated production planning and scheduling system for hybrid flowshop organizations," International Journal of Production Economics, Elsevier, vol. 74(1-3), pages 33-48, December.
    12. Christian Artigues & Dominique Feillet, 2008. "A branch and bound method for the job-shop problem with sequence-dependent setup times," Annals of Operations Research, Springer, vol. 159(1), pages 135-159, March.
    13. Aristide Mingozzi & Vittorio Maniezzo & Salvatore Ricciardelli & Lucio Bianco, 1998. "An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation," Management Science, INFORMS, vol. 44(5), pages 714-729, May.
    14. Sawik, Tadeusz, 2002. "Monolithic vs. hierarchical balancing and scheduling of a flexible assembly line," European Journal of Operational Research, Elsevier, vol. 143(1), pages 115-124, November.
    15. 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.
    16. Shanker, Kripa & Modi, Bimal K., 1999. "A branch and bound based heuristic for multi-product resource constrained scheduling problem in FMS environment," European Journal of Operational Research, Elsevier, vol. 113(1), pages 80-90, February.
    Full references (including those not matched with items on IDEAS)

    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. Alexander Tesch, 2020. "A polyhedral study of event-based models for the resource-constrained project scheduling problem," Journal of Scheduling, Springer, vol. 23(2), pages 233-251, April.
    2. Andrei Horbach, 2010. "A Boolean satisfiability approach to the resource-constrained project scheduling problem," Annals of Operations Research, Springer, vol. 181(1), pages 89-107, December.
    3. Florian Mischek & Nysret Musliu, 2021. "A local search framework for industrial test laboratory scheduling," Annals of Operations Research, Springer, vol. 302(2), pages 533-562, July.
    4. Florian Mischek & Nysret Musliu & Andrea Schaerf, 2023. "Local search approaches for the test laboratory scheduling problem with variable task grouping," Journal of Scheduling, Springer, vol. 26(5), pages 457-477, October.
    5. Bernardo F. Almeida & Isabel Correia & Francisco Saldanha-da-Gama, 2018. "A biased random-key genetic algorithm for the project scheduling problem with flexible resources," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(2), pages 283-308, July.
    6. Chen, Jiaqiong & Askin, Ronald G., 2009. "Project selection, scheduling and resource allocation with time dependent returns," European Journal of Operational Research, Elsevier, vol. 193(1), pages 23-34, February.
    7. Brucker, Peter & Knust, Sigrid, 2003. "Lower bounds for resource-constrained project scheduling problems," European Journal of Operational Research, Elsevier, vol. 149(2), pages 302-313, September.
    8. Estévez-Fernández, Arantza, 2012. "A game theoretical approach to sharing penalties and rewards in projects," European Journal of Operational Research, Elsevier, vol. 216(3), pages 647-657.
    9. Rolf H. Möhring & Andreas S. Schulz & Frederik Stork & Marc Uetz, 2003. "Solving Project Scheduling Problems by Minimum Cut Computations," Management Science, INFORMS, vol. 49(3), pages 330-350, March.
    10. Debels, Dieter & De Reyck, Bert & Leus, Roel & Vanhoucke, Mario, 2006. "A hybrid scatter search/electromagnetism meta-heuristic for project scheduling," European Journal of Operational Research, Elsevier, vol. 169(2), pages 638-653, March.
    11. Roland Braune & Karl F. Doerner, 2017. "Real-world flexible resource profile scheduling with multiple criteria: learning scalarization functions for MIP and heuristic approaches," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(8), pages 952-972, August.
    12. Guo, Weikang & Vanhoucke, Mario & Coelho, José, 2023. "A prediction model for ranking branch-and-bound procedures for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 579-595.
    13. Guidong Zhu & Jonathan F. Bard & Gang Yu, 2006. "A Branch-and-Cut Procedure for the Multimode Resource-Constrained Project-Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 18(3), pages 377-390, August.
    14. Valls, Vicente & Ballestin, Francisco & Quintanilla, Sacramento, 2005. "Justification and RCPSP: A technique that pays," European Journal of Operational Research, Elsevier, vol. 165(2), pages 375-386, September.
    15. Luise-Sophie Hoffmann & Carolin Kellenbrink & Stefan Helber, 2020. "Simultaneous structuring and scheduling of multiple projects with flexible project structures," Journal of Business Economics, Springer, vol. 90(5), pages 679-711, June.
    16. Xiaowei Lin & Jing Zhou & Lianmin Zhang & Yinlian Zeng, 2021. "Revenue sharing for resource reallocation among project activity contractors," Annals of Operations Research, Springer, vol. 301(1), pages 121-141, June.
    17. Klein, Robert, 2000. "Bidirectional planning: improving priority rule-based heuristics for scheduling resource-constrained projects," European Journal of Operational Research, Elsevier, vol. 127(3), pages 619-638, December.
    18. Servranckx, Tom & Vanhoucke, Mario, 2019. "A tabu search procedure for the resource-constrained project scheduling problem with alternative subgraphs," European Journal of Operational Research, Elsevier, vol. 273(3), pages 841-860.
    19. Kellenbrink, Carolin & Helber, Stefan, 2015. "Scheduling resource-constrained projects with a flexible project structure," European Journal of Operational Research, Elsevier, vol. 246(2), pages 379-391.
    20. Zhengwen He & Nengmin Wang & Pengxiang Li, 2014. "Simulated annealing for financing cost distribution based project payment scheduling from a joint perspective," Annals of Operations Research, Springer, vol. 213(1), pages 203-220, February.

    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:spr:annopr:v:206:y:2013:i:1:p:311-339:10.1007/s10479-012-1256-5. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.