Heuristics for scheduling in a no-wait open shop with movable dedicated machines

In this paper, we address a scheduling problem related to people's livelihood, such as road construction works that include laying pipes for gas, water and phone. The problem is a multi-processing-stage open shop with the characteristics of movable dedicated machines and no-wait restriction, also known as no intermediate queue. The objective is to schedule the jobs such that the total occupation time for all the processing stages is minimized. Some two-phase heuristic algorithms are proposed for solving the problem. Computational results show that the heuristic is fairly effective in finding an optimal or a near-optimal solution for small-sized problems.