An exact algorithm for the bi-objective timing problem |
| |
Authors: | Sophie Jacquin Fanny Dufossé Laetitia Jourdan |
| |
Affiliation: | 1.Inria Lille - Nord Europe, ORKAD, CRIStAL,University of Lille 1,Villeneuve d’Ascq,France |
| |
Abstract: | The timing problem in the bi-objective just-in-time single-machine job-shop scheduling problem (JiT-JSP) is the task to schedule N jobs whose order is fixed, with each job incurring a linear earliness penalty for finishing ahead of its due date and a linear tardiness penalty for finishing after its due date. The goal is to minimize the earliness and tardiness simultaneously. We propose an exact greedy algorithm that finds the entire Pareto front in (O(N^2)) time. This algorithm is asymptotically optimal. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|