Abstract:This paper considers several scheduling problems where deliveries are made in batches with each batch delivered to the customer in a single shipment. Various scheduling costs, which are based on the limited delivery times of the jobs, are considered. The objective is to minimize the scheduling cost plus the delivery cost. When the jobs are same, with same processing time and same weight, production costs is decreasing function on the delivery times, but delivery cost is increasing function on the delivery times. Therefore, binary search is used to find the optimal delivery times, and the problem can be solved in polynomial times.