Abstract:

There are a variety of joint job production and transportation scheduling
problems that arise in modern manufacturing systems. In this paper, we study one of
such problems that arises in a flowshop environment where there are two processing
stages and a single transporter that is available to deliver the finished jobs from the
first stage to the second. There is a single machine in the first stage and two parallel
machines in the second stage. The transporter can carry only one job in each
shipment. Each job is first processed on the single machine at stage one, then
transported to and processed on one of the two parallel machines at stage two. The
objective is to minimize the makespan, i.e., the completion time of the last job in the
second stage. Since this problem is strongly NP-hard, we propose a fast heuristic
and show that the heuristic has a worst-case bound of 5/2. We also conduct
numerical experiments to evaluate the average performance of this heuristic.