A hybrid two-stage transportation and batch scheduling problem

We study the coordinated scheduling problem of hybrid batch production on a single batching machine and two-stage transportation connecting the production, where there is a crane available in the first-stage transportation that transports jobs from the warehouse to the machine and there is a vehicle available in the second-stage transportation to deliver jobs from the machine to the customer. As the job to be carried out is big and heavy in the steel industry, it is reasonable assumed that both the crane and the vehicle have unit capacity. The batching machine processes a batch of jobs simultaneously. Each batch occur a setup cost. The objective is to minimize the sum of the makespan and the total setup cost. We prove that this problem is strongly NP-hard. A polynomial time algorithm is proposed for a case where the job transportation times are identical on the crane or the vehicle. An efficient heuristic algorithm for the general problem is constructed and its tight worst-case bound is analyzed. In order to further verify the performance of the proposed heuristics, we develop a lower bound on the optimal objective function. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances.