Bicriteria Scheduling on a Single Batching Machine with Transportation and Deterioration to Minimize Total Completion Time and Production Costs

摘要

In this paper, we consider a coordinated scheduling problem on a single batching machine with transportation and deterioration. The jobs are transported by a vehicle to the single batching machine for further processing. The processing time of a job is a step increasing function of its exposure time which is equivalent to the time interval from the beginning of the transportation to the starting of the job on the machine. The objective is to find Pareto-optimal schedules with two performance criteria (total completion time and the number of batches) to balance the inventory level and the production costs. We prove that the general problem is strongly NP-hard. We further develop polynomial-time algorithms for two special cases with a fixed job sequence and without exposure time limit, respectively. For the general problem, we develop a heuristic algorithm and a branch and bound algorithm. Computational experiments show that the heuristic algorithms perform well on randomly generated problem instances, and the branch and bound algorithm can obtain Pareto-optimal solutions for the small-scaled instances.