Casos especiales solucionables en tiempo polinomial del problema de calendarización con tiempos de liberación y fechas limites en una maquina

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).