89. When does solving just-in-time scheduling problem with non-restrictive due date guarantee solution to the CON problem with same performances?
Invited abstract in session FD-1: Fairness, stream Fairness.
Friday, 15:30 - 17:00Room: L226
Authors (first author is the speaker)
| 1. | Ameur SOUKHAL
|
| LIFAT, University of Tours | |
| 2. | Nguyen HUYNH-TUONG
|
| Industrial University of Ho Chi Minh City |
Abstract
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 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.
Keywords
- Scheduling
- Algorithms
Status: accepted
Back to the list of papers