A two stage scheduling with transportation and batching

作者：Zhu Hongli^*

来源：Information Processing Letters, 2012, 112(19): 728-731.

DOI：10.1016/j.ipl.2012.06.013

• Scheduling
• Transportation
• NP-hard
• Fully polynomial time approximation scheme

We investigate a two stage scheduling problem with transportation and batching, in which jobs are transported from holding area to the batching machine by in 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 botching 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 = 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.

• 出版日期2012-10-15
• 单位北京航空航天大学