Minimizing the earliness–tardiness for the customer order scheduling problem in a dedicated machine environment

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

Abstract

The 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.

Details

OriginalspracheEnglisch
Seitenumfang19
Fachzeitschrift Journal of scheduling : JOS
Jahrgang2024
Ausgabenummer6
PublikationsstatusVeröffentlicht - 13 Okt. 2024
Peer-Review-StatusJa

Externe IDs

ORCID /0000-0003-0753-0517/work/169642876
ORCID /0000-0003-4711-2184/work/169640485

Schlagworte

Schlagwörter

  • Customer order scheduling, Dedicated machines, Earliness–tardiness, Iterated greedy algorithm, Machine scheduling, Metaheuristics