Decisions, Operations, and Technology Management

This paper discusses the complexity of deterministic scheduling of customer orders. The problem is as follows. Each customer order (job) consists of at most two items, to be processed on a dedicated machine. Items of customer orders are immediately available for processing. The objective is to minimize the average completion time of the customer orders, that is the times until all items of a customer order have been processed. The problem is shown to be NP-hard in the strong sense.