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

Ting-Chun Lo and Bertrand M. T. Lin
Additional contact information
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

Mathematics, 2021, vol. 9, issue 13, 1-35

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.

Keywords: resource-constrained scheduling; relocation problem; flow shop; resource recycling; heuristic algorithms; ant colony optimization (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/13/1527/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/13/1527/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:13:p:1527-:d:584782

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().