<figure><img src="image_1.png" /></figure>

HAL
open science

# When does solving just-in-time scheduling problem with non-restrictive due date guarantee solution to the CON problem with same performances?

Ameur Soukhal, Nguyen Huynh Tuong

► To cite this version:

Ameur Soukhal, Nguyen Huynh Tuong. When does solving just-in-time scheduling problem with non-restrictive due date guarantee solution to the CON problem with same performances?. ECCO XXXVII CONFERENCE, Jun 2024, Ghent (BE), Belgium. hal-04827521

HAL Id: hal-04827521

https://hal.science/hal-04827521v1

Submitted on 9 Dec 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
When does solving just-in-time scheduling problem with non-restrictive due date guarantee
solution to the CON problem with same performances?

Ameur Soukhal¹*, Nguyen Huyng-Tuong²

¹LIFAT, University of Tours, Tours, France
ameur.soukhal@univ-tours.fr

²Industrial University of Ho Chi Minh City, Ho Chi Minh, Vietnam
htnguyen@iuh.edu.vn

**Keywords:** Scheduling problems - Just-In-Time scheduling - common due date – Approximation schemes

This study addresses the scheduling of n independent jobs on a single machine to minimize total weighted earliness and tardiness penalties. This entails completing the jobs as closely as possible to their due date. Known as Just-In-Time (JIT) scheduling problems, they have relevance to numerous industrial applications. One classical JIT problem is the model introduced by Kanet in 1981, wherein all jobs share a common due date. Such a model corresponds, for example, to an assembly system where the components of a product should be ready simultaneously, or when it involves an order from a customer that must be delivered by a predetermined date.

The earliness (and tardiness) of each job corresponds to the time elapsed from its early (or late) completion until its due date. Primarily, two families of JIT scheduling problems on a single machine are examined:

* JIT with an unrestricted common due date, denoted unres: when the common due date is greater than the sum of processing times.

* JIT with a controllable common due date, denoted CON "Constant Flow Allowance": the common due date is a decision variable with an associated cost.

Initially focusing on unres scheduling problems, some cases are proven to be polynomial: the symmetric case (where the earliness penalty of a job is identical to its tardiness penalty) and the case where processing times are identical. For the general case and under certain conditions on the earliness penalties, it is demonstrated that the unres JIT scheduling problem admits a PTAS (Polynomial Time Approximation Scheme).

Motivated by the investigation of the existence of a strong link between these two families of JIT problems (unres vs CON), we have demonstrated through polynomial reductions how optimal solutions or approximation schemes (FPTAS and PTAS) for CON can be derived from solving the unres problems.