IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2021i13p1527-d584782.html
   My bibliography  Save this article

Relocation Scheduling in a Two-Machine Flow Shop with Resource Recycling Operations

Author

Listed:
  • Ting-Chun Lo

    (Institute of Information Management, National Yang Ming Chiao Tung University, Hsinchu 300, Taiwan)

  • Bertrand M. T. Lin

    (Institute of Information Management, National Yang Ming Chiao Tung University, Hsinchu 300, Taiwan)

Abstract

This paper considers a variant of the relocation problem, which is formulated from an urban renewal project. There is a set of jobs to be processed in a two-machine flow shop subject to a given initial resource level. Each job consumes some units of the resource to start its processing on machine 1 and will return some amount of the resource when it is completed on machine 2. The amount of resource released by a job is not necessarily equal to the amount of resource acquired by the job for starting the process. Subject to the resource constraint, the problem is to find a feasible schedule whose makespan is minimum. In this paper, we first prove the NP-hardness of two special cases. Two heuristic algorithms with different processing characteristics, permutation and non-permutation, are designed to construct feasible schedules. Ant colony optimization (ACO) algorithms are also proposed to produce approximate solutions. We design and conduct computational experiments to appraise the performances of the proposed algorithms.

Suggested Citation

  • 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.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:13:p:1527-:d:584782
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/13/1527/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/13/1527/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Edward H. Kaplan & Oded Berman, 1988. "OR Hits the Heights: Relocation Planning at the Orient Heights Housing Project," Interfaces, INFORMS, vol. 18(6), pages 14-22, December.
    2. 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.
    3. Kaplan, Edward H. & Amir, Amihood, 1988. "A fast feasibility test for relocation problems," European Journal of Operational Research, Elsevier, vol. 35(2), pages 201-206, May.
    4. Lin, B. M. T. & Cheng, T. C. E., 1999. "Minimizing the weighted number of tardy jobs and maximum tardiness in relocation problem with due date constraints," European Journal of Operational Research, Elsevier, vol. 116(1), pages 183-193, July.
    5. Lin, B.M.T. & Liu, S.T., 2008. "Maximizing the reward in the relocation problem with generalized due dates," International Journal of Production Economics, Elsevier, vol. 115(1), pages 55-63, September.
    6. 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.
    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. Jian-You Xu & Win-Chin Lin & Yu-Wei Chang & Yu-Hsiang Chung & Juin-Han Chen & Chin-Chia Wu, 2023. "A Two-Machine Learning Date Flow-Shop Scheduling Problem with Heuristics and Population-Based GA to Minimize the Makespan," Mathematics, MDPI, vol. 11(19), pages 1-21, September.

    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. Lin, B.M.T. & Liu, S.T., 2008. "Maximizing the reward in the relocation problem with generalized due dates," International Journal of Production Economics, Elsevier, vol. 115(1), pages 55-63, September.
    2. Edward H. Kaplan, 2021. "Perspectives on Policy Modeling: 2018 MSOM Fellow Award," Manufacturing & Service Operations Management, INFORMS, vol. 23(2), pages 267-273, March.
    3. Asbach, Lasse & Dorndorf, Ulrich & Pesch, Erwin, 2009. "Analysis, modeling and solution of the concrete delivery problem," European Journal of Operational Research, Elsevier, vol. 193(3), pages 820-835, March.
    4. Wendi Tian & Erik Demeulemeester, 2014. "Railway scheduling reduces the expected project makespan over roadrunner scheduling in a multi-mode project scheduling environment," Annals of Operations Research, Springer, vol. 213(1), pages 271-291, February.
    5. Byung-Cheon Choi & Changmuk Kang, 2019. "A linear time–cost tradeoff problem with multiple milestones under a comb graph," Journal of Combinatorial Optimization, Springer, vol. 38(2), pages 341-361, August.
    6. Andrzej Kozik, 2017. "Handling precedence constraints in scheduling problems by the sequence pair representation," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 445-472, February.
    7. Xiong, Jian & Leus, Roel & Yang, Zhenyu & Abbass, Hussein A., 2016. "Evolutionary multi-objective resource allocation and scheduling in the Chinese navigation satellite system project," European Journal of Operational Research, Elsevier, vol. 251(2), pages 662-675.
    8. 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.
    9. Ilkyeong Moon & Sanghyup Lee & Moonsoo Shin & Kwangyeol Ryu, 2016. "Evolutionary resource assignment for workload-based production scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(2), pages 375-388, April.
    10. Park, Jongyoon & Han, Jinil & Lee, Kyungsik, 2024. "Integer optimization models and algorithms for the multi-period non-shareable resource allocation problem," European Journal of Operational Research, Elsevier, vol. 317(1), pages 43-59.
    11. Mattfeld, D. C. & Kopfer, H., 2003. "Terminal operations management in vehicle transshipment," Transportation Research Part A: Policy and Practice, Elsevier, vol. 37(5), pages 435-452, June.
    12. M. Vanhoucke, 2006. "A scatter search procedure for maximizing the net present value of a project under renewable resource constraints," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 06/417, Ghent University, Faculty of Economics and Business Administration.
    13. Ip, W. H. & Yung, K. L. & Wang, Dingwei, 2004. "A branch and bound algorithm for sub-contractor selection in agile manufacturing environment," International Journal of Production Economics, Elsevier, vol. 87(2), pages 195-205, January.
    14. Dieter Debels & Mario Vanhoucke, 2007. "A Decomposition-Based Genetic Algorithm for the Resource-Constrained Project-Scheduling Problem," Operations Research, INFORMS, vol. 55(3), pages 457-469, June.
    15. Yamashita, Denise Sato & Armentano, Vinicius Amaral & Laguna, Manuel, 2006. "Scatter search for project scheduling with resource availability cost," European Journal of Operational Research, Elsevier, vol. 169(2), pages 623-637, March.
    16. Moukrim, Aziz & Quilliot, Alain & Toussaint, Hélène, 2015. "An effective branch-and-price algorithm for the Preemptive Resource Constrained Project Scheduling Problem based on minimal Interval Order Enumeration," European Journal of Operational Research, Elsevier, vol. 244(2), pages 360-368.
    17. Eugene Shragowitz & Habib Youssef & Bing Lu, 2003. "Iterative Converging Algorithms for Computing Bounds on Durations of Activities in Pert and Pert-Like Models," Journal of Combinatorial Optimization, Springer, vol. 7(1), pages 5-22, March.
    18. Hongbo Li & Zhe Xu & Wenchao Wei, 2018. "Bi-Objective Scheduling Optimization for Discrete Time/Cost Trade-Off in Projects," Sustainability, MDPI, vol. 10(8), pages 1-15, August.
    19. Dorndorf, Ulrich & Drexl, Andreas & Nikulin, Yury & Pesch, Erwin, 2005. "Flight gate scheduling: State-of-the-art and recent developments," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 584, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    20. 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.

    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:gam:jmathe:v:9:y:2021:i:13:p:1527-:d:584782. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.