AbstractThe customer order scheduling problem has garnered considerable attention in the recent scheduling literature. It is assumed that each of several customer orders consists of several jobs, and each customer order is completed only if each job of the order is completed. In this paper, we consider the customer order scheduling problem in a machine environment where each customer places exactly one job on each machine. The objective is to minimize the earliness–tardiness, where tardiness is defined as the time an order is finished past its due date, and earliness is the time a job is finished before its due date or the completion time of the corresponding order, whichever is later. Even though the earliness–tardiness criterion is an important objective for just-in-time production, this problem has not been studied in the context of the customer order scheduling problem. We provide a mixed-integer linear programming (MILP) formulation for this problem and derive multiple problem properties. Furthermore, we develop six different heuristics for this problem configuration. They follow the structure of the iterated greedy algorithm and additionally use a refinement function in which they differ. In a computational experiment, the algorithms were compared with each other and outperformed a solver solution of the MILP, which proves their ability to efficiently solve the problem configuration.