A coordinated scheduling of production-and-delivery under dynamic delivery cost environments

• Production and delivery scheduling, where delivery cost depends on time period.
• The objective is to minimize sum of the scheduling cost and delivery cost.
• The problem is proved to be strongly NP-hard for all the objective measures.
• Some associated dynamic programming algorithms are derived.

This paper considers a coordination scheduling of production and delivery, where delivery cost depends on time period for delivery, but not dependent on individual jobs. The objective is to find a coordinated production-and-delivery schedule to minimize sum of the scheduling cost (either one of makespan, sum of completion times, or maximum lateness) and delivery cost. The problem is proved to be strongly NP-hard for all the objective measures tested. Some restricted cases of the problem are also characterized for their complexities, for which the associated dynamic programming algorithms are derived.