Título
Casos especiales solucionables en tiempo polinomial del problema de calendarización con tiempos de liberación y fechas limites en una maquina
Autor
MARIA ELISA CHINOS OLIVAN
Colaborador
Nodari Vakhania
Nivel de Acceso
Acceso Abierto
Resumen o descripción
Resumen
Los problemas de optimizaci on combinatoria (CO, por sus siglas en ingl es)
constituyen una clase relevante de problemas pr acticos con una naturaleza
discreta.
Los problemas de CO se pueden clasi car en dos clases: los problemas P, los
cuales se pueden resolver en tiempo polinomial con respecto al tama~no de
una instancia, y los problemas NP-duro. Existen algoritmos e cientes para
los problemas de la clase P, y se piensa que no existen algoritmos e cientes
para los problemas NP-duro.
El problema de calendarizaci on que estudiamos en este proyecto de investigaci
on es de la clase de los problemas de optimizaci on combinatoria. El
t ermino de calendarizaci on se re ere a la asignaci on de un conjunto de solicitudes
sobre un conjunto dado de recursos a lo largo del tiempo con el
objetivo de optimizar un criterio objetivo dado. Las solicitudes son llamadas
trabajos o tareas y los recursos son llamados m aquinas o procesadores, mientras
que el objetivo es elegir el orden de procesamiento de los trabajos sobre
las m aquinas as como cumplir con un criterio objetivo dado.
Diferentes caracter sticas de los trabajos y de las m aquinas junto con diferentes
criterios de optimalidad dan origen a una gran cantidad de problemas
de calendarizaci on.
El problema de calendarizaci on b asico que consideramos en este proyecto de
investiagaci on es el siguiente: n trabajos tienen que ser calendarizados en
una m aquina. Cada trabajo i llega a ser disponible en su tiempo de libera-
ci on o cabeza ri, y necesita un tiempo de procesamiento continuo pi sobre
la m aquina. La m aquina s olo puede procesar un trabajo a la vez. Una vez
que el trabajo j es completado este trabajo todav a necesita un tiempo de
entrega (constante) qi para su complet es total (los trabajos son entregados
v
vi
por una unidad independiente y este no toma tiempo en la m aquina). Todos
estos par ametros son enteros. Nuestro objetivo es encontrar una secuencia
de trabajos sobre la m aquina que minimice el m aximo tiempo de complet es
total.
Garey y Johnson en 1979 demostraron que el problema de calendarizacin
que consideramos en este trabajo denotado por 1jrj ; qj jCm ax es NP-duro
en el sentido estricto. Un m etodo aproximado para solucionar el problema
1jrj ; qj jCm ax es la llamada heur stica extendida de Jackson (JE-heur stica),
dada por Schrage en 1971. La JE-heur stica iterativamente, en cada tiempo
de calendarizaci on t (dado por el tiempo de liberaci on o complet es de un
trabajo), entre los trabajos liberados en este tiempo t calendariza uno con el
mayor tiempo de entrega.
Explorando las propiedades estructurales inherentes del problema, derivamos
nuevas condiciones de optimalidad cuando algunos casos pr acticos del
problema 1jrj ; qj jCm ax pueden resolverse de manera optima en un tiempo polinomial.
En particular, proporcionamos condiciones expl citas que conducen
a una soluci on e ciente del problema 1jrj ; qj jCm ax mediante una mera aplicaci
on de la JE-heur stica. Adem as estudiamos otras propiedades estructurales
utiles de los JE-calendarios (los creados por la JE-heur stica) que conducen
a la soluci on optima de otras versiones de nuestro problema con el mismo
costo computacional que el de la JE-heur stica.
Finalmente, nos enfocamos en un caso especial de nuestro problema con solo
dos tiempos permitidos de liberaci on de los trabajo r1 y r2 con r1 < r2
(denotado como 1jfr1; r2g; fd1; d2gjLm ax), demostramos que este problema es
NP-duro. Para este problema, tambi en buscamos reglas de dominio estrictas
y condiciones de optimalidad que se pueden veri car en tiempo polinomial.
Abstract
Combinatorial optimization (CO) problems constitute a signi cant class of
practical problems with a discrete nature.
A CO problem is characterized by a nite set of the so-called feasible solutions,
de ned by a given set of restrictions, and an objective function for
these feasible solutions, which typically needs to be optimized, i.e., minimized
or maximized: the problem is to nd an optimal solution, that is, one
minimizing the objective function.
The CO problems are partitioned into two basic types, type P , which are
polynomially solvable ones, and NP �����hard problems. Intuitively, there exist
e cient (polynomial in the size of the problem) solution methods or algorithms
for the problems from the rst class, whereas no such algorithms exist
for the problems of the second class.
The scheduling problem that we study in this project is of the class of problems
of combinatorial optimization.The term scheduling refers to the assignment
of a set of requests to the given set of resources over time with the
objective to optimize a given objective criterion. The requests are called jobs
or tasks and a resources are called machines or processors, whereas the aim is
to choose the order of processing the jobs on the machines so as to meet a given
objective criteria. Di erent characteristics of jobs and machines together
with di erent optimality criteria originate a vast amount of the scheduling
problems.
A basic scheduling problem that we consider in this thesis is as follows: n
jobs have to be scheduled on a single machine. Each job j becomes available
at its release time rj . A released job can be assigned to the machine that has
to process job j for pj time units. The machine can handle at most one job at
a time. Once it complet es j this job still needs a (constant) delivery time qj
vii
viii
for its full completion (the jobs are delivered by an independent unit and this
takes no machine time). All above parameters are integers. Our objective is
to nd a job sequence on the machine that minimizes the maximum job full
completion time.
Garey and Johnson in 1979 showed that our scheduling problem denoted by
1jrj ; qj jCm ax it is NP-hard in the strict sense.
An approximate method to solve this problem is the so called extended Jackson
heuristic (JE-heuristic), given by Schrage in 1971. The JE-heuristic
iteratively, at each scheduling time t (given by job release or completion time),
among the jobs released by time t schedules one with the the largest
delivery time (or smallest due-date).
Exploring the inherent structural properties of the problem, here we derive
new optimality conditions when practical special cases of our problem can be
solved optimally in a low degree polynomial time. In particular, we provide
explicit conditions that lead to an e cient solution of the problem by a mere
application of J-heuristic. Then we study further useful structural properties
of the J-schedules (ones created by J-heuristic) leading to the optimal solution
of other versions of the problem with the same computational cost as that of
J-heuristic.
Finally, we focus on a special case of our problem with only two allowable job
release times r1 and r2 with r1 < r2 (abbreviated 1jfr1; r2g; fd1; d2gjLm ax).
Although the latter problem remains NP-hard, it admits stricter dominance
rules and optimality conditions leading to the corresponding polynomial-time
veri cation procedures (and the reduction of the search space).
Editor
El autor
Fecha de publicación
9 de noviembre de 2018
Tipo de publicación
Tesis de doctorado
Recurso de información
Formato
Idioma
Español
Cobertura
MEX
Audiencia
Investigadores
Repositorio Orígen
Repositorio Institucional de Acceso Abierto de la Universidad Autónoma del Estado de Morelos
Descargas
0