Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



On the local dominance properties in single machine scheduling problems
Indexado
WoS WOS:001147645000001
Scopus SCOPUS_ID:85182985854
DOI 10.1007/S10479-023-05801-9
Año 2024
Tipo artículo de investigación

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



We consider a non-preemptive singlemachine scheduling problem for a non-negative penalty function f, where an optimal schedule satisfies the left-shifted property, i.e. in any optimal sequence all executions happen without idle time with a starting time t(0) >= 0. For this problem, every job j has a priority weight w(j) and a processing time p(j), and the goal is to find an order on the given jobs that minimizes Sigma w(j) f (C-j), where C-j is the completion time of job j. This paper explores local dominance properties, which provide a powerful theoretical tool to better describe the structure of optimal solutions by identifying rules that at least one optimal solution must satisfy. We propose a novel approach, which allows to prove that the number of sequences that respect the local dominance property among three jobs is only two, not three, reducing the search space from n! to n!/3((sic)n/3(sic)) schedules. In addition, we define some non-trivial cases for the problem with a strictly convex penalty function that admits an optimal schedule, where the jobs are ordered in non-increasing weight. Finally, we provide some insights into three future research directions based on our results (i) to reduce the number of steps required by an exact exponential algorithm to solve the problem, (ii) to incorporate the dominance properties as valid inequalities in a mathematical formulation to speed up implicit enumeration methods, and (iii) to show the computational complexity of the problem of minimizing the sum of weighted mean squared deviation of the completion times with respect to a common due date for jobs with arbitrary weights, whose status is still open.

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Operations Research & Management Science
Scopus
Sin Disciplinas
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 Jorquera Bravo, Natalia Mujer Universidad de Santiago de Chile - Chile
Inst Polytech Paris - Francia
Ctr Etud & Rech Informat & Commun CEDRIC - Francia
Unité de mathématiques appliquées - Francia
Conservatoire National des Arts et Metiers - Francia
2 Vasquez, Oscar C. - Universidad de Santiago de Chile - Chile

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
Proyecto FONDECYT
Beca de Postdoctorado en el Extranjero
ANID

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
The authors are grateful for partial support by ANID, Beca de Postdoctorado en el Extranjero, Folio: 74200020, ANID, Beca de doctorado en el extranjero, Folio: 72220350, and ANID, Proyecto FONDECYT, Folio: 1211640.

Muestra la fuente de financiamiento declarada en la publicación.