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

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