Single machine batch scheduling to minimize the sum of total flow time and batch delivery cost with an unavailability interval

• DOI: 10.1016/j.ins.2014.02.142
• Publication Date: 2014-03-16T01:30:54Z
• Authors: Yunqiang Yin; Deshi Ye; Guochuan Zhang
• Keywords: Unavailability; Polynomial-time approximation scheme; Rounding; Tardiness; Due date; Holding cost

This paper addresses the problem of scheduling n nonresumable and simultaneously available jobs on a single machine, where the machine has a fixed unavailability interval, and the jobs are delivered in batches to the customers. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The goal is to find the optimal delivery date for each job and an optimal job sequence to minimize the sum of total flow time and batch delivery cost. The problem is shown to be NP-hard based on a reduction from the Equal-Size Partition Problem. Then a pseudo-polynomial time algorithm is developed, establishing that it is NP-hard in the ordinary sense. Finally, by applying the interval partitioning technique and the rounding technique, a fully polynomial time approximation scheme (FPTAS) and a bicriteria fully polynomial time approximation scheme are developed, which run in time On5e2+n5logn and On6e, respectively.