A two stage scheduling with transportation and batching

We investigate a two stage scheduling problem with transportation and batching, in which jobs are transported from holding area to the batching machine by m   vehicles in the first stage. Each vehicle can transport only one job at a time. As the job is big and heavy in the steel industry, it is reasonable to assume that the vehicle capacity is unit. In the second stage, the batching machine can process up to a fixed number of jobs as a batch simultaneously. Each bath to be processed occurs a processing cost. Our objective is to minimize the makespan and processing cost. For m=1m=1, we present a polynomial time algorithm. For the general problem we prove that it is NP-hard in ordinary sense. Then we provide a pseudo-polynomial time algorithm and obtain a fully polynomial time approximation scheme.

► In this paper, we investigate a two stage scheduling problem with transportation and batching to minimize the makespan and processing cost. ► A polynomial time algorithm for a special case when m=1m=1 is presented. ► It is proved NP-hard in ordinary sense for the general problem. ► A pseudo-polynomial time algorithm and a fully polynomial time approximation scheme are provided.