Asignación de recursos a actividades fijas.

VIII Cong eso de Ingenie ía de O ganización Leganés, 9 y 10 de sep iemb e de 2004 Asignación de ecu sos a ac i idades ijas José Manuel Ga cía Sánchez, Rica do Galán de Vega Dp o. O ganización Indus ial y Ges ión de Emp esas. Escuela Supe io de Ingenie os. Uni e sidad de Se illa. Camino de los Descub imien os, s/n 41092 Se illa. [email p o ec ed], [email p o ec ed] Resumen La asignación de ecu sos a ac i idades ijas se ca ac e iza como el p oblema de p og ama una se ie de abajos sob e un conjun o de máquinas en pa alelo. Cada abajo posee un ins an e ijo de comienzo, un ins an e ijo de inalización, un peso y pe enece a un ipo de abajo. Respec o a las máquinas, puede conside a se un cos e asociado al uso de la máquina y, en ocasiones, uno o a ios in e alos de iempo en el que únicamen e es á disponible. El p oblema es conocido en la li e a u a como Fixed Job Scheduling P oblem (FSP). En es e abajo se ealiza una clasi icación y e isión bibliog á ica de odos los p oblemas de ipo FSP exis en es en la li e a u a, p esen ando las ca ac e ís icas de cada uno de ellos, las écnicas de esolución empleadas, el ipo de p oblema en o den a su complejidad y las aplicaciones p ác icas exis en es del p oblema. Palab as cla e: Asignación, T abajos ijos, Re isión bibliog á ica. 1. In oducción La asignación de ecu sos a ac i idades ijas se conoce como el p oblema de p og ama una se ie de abajos sob e un conjun o de máquinas en pa alelo. Los abajos o ac i idades ienen que se ealizados den o de un in e alo empo al ijo, siendo inadmisible la ealización pa cial o o al ue a del mismo. Las máquinas son el ecu so necesa io pa a ealiza los abajos. Cada abajo consume un iempo ijo de ocupación de la máquina. La eo ía de la asignación de ecu sos a ac i idades ijas, que pod ía se ambién denominada como eo ía de la p og amación de abajos en in e alos ijos sob e máquinas en pa alelo, aba ca p oblemas de dos ipos. Po un lado, p oblemas donde el in e alo pa a el p oceso de cada abajo coincide con el iempo de du ación del abajo, es deci , no exis e ninguna holgu a pa a el p ocesamien o del abajo. Po o o lado, p oblemas donde el in e alo de iempo pa a el p ocesamien o de cada abajo es mayo o igual al iempo de p oceso del abajo. El p ime ipo de p oblemas es denominado en la li e a u a como Fixed Job Scheduling P oblem (FSP) mien as que el segundo se conoce como Va iable Job Scheduling P oblem (VSP). En es e abajo p e endemos ealiza una clasi icación y e isión bibliog á ica de odos los p oblemas de ipo FSP exis en es en la li e a u a, p esen ando las ca ac e ís icas de cada uno de ellos, las écnicas de esolución empleadas, el ipo de p oblema en o den a su complejidad y las aplicaciones p ác icas exis en es. 127 2. De inición y Clasi icación del p oblema FSP De la o ma más gené ica, el p oblema de la asignación de ecu sos a ac i idades o abajos ijos(FSP) p esen a las siguien es ca ac e ís icas: - Dado un conjun o de n abajos N={J1,..,Ji, ...Jn}, cada uno con un ins an e ijo de comienzo si, un ins an e ijo de inalización i, un peso o alo wi y una clase de abajo ai a la que pe enece. - Dado un conjun o de m máquinas, las cuales pe enecen a una clase de máquina bj y lle an asociado un cos e ijo cj po su uso. - Po o o lado se de ine un in e alo de iempo [ j, ej] pa a cada máquina en el que únicamen e es á disponible. - Pa a el p oblema se de inen A di e en es clases de abajos y B clases de máquinas. Las es icciones asociadas al p ocesamien o de los abajos son: - Cada máquina puede ealiza un solo abajo en un mismo ins an e de iempo. - Cada abajo puede se ealizado sob e un subconjun o de máquinas. Se asume que cada clase de máquina puede ealiza abajos pe enecien es a un núme o limi ado de clases de abajos. Po ello se de ine una ma iz de compa ibilidad L en e clases de máquinas y abajos cuyos alo es pueden se : 1 es compa ible con maquina si y (,)0 en o o caso iji AC JMa L L ila col × ==  ==   j ilaccol La clasi icación del p oblema se ealiza, p incipalmen e, en o no a los siguien es pa áme os: 1) Obje i os del p oblema 2) Núme o de clases de máquinas y abajos 1. Obje i os del p oblema. En el p oblema se conside an es obje i os undamen almen e: 1.1 Minimiza el cos e o al en máquinas eque idas pa a p ocesa odos los abajos. Cuando el cos e es la unidad, o no se conside a, el obje i o se en iende como minimiza el núme o mínimo de máquinas necesa ias pa a p ocesa odos los abajos. Se supone un núme o su icien e de máquinas pa a pode ealiza odos los abajos. 1.2 A e igua si, dado un conjun o de máquinas, es posible ealiza odos los abajos exis en es (obje i o aplicado en el caso de posee a ias clases de abajos y máquinas). 1.3 A pa i de un núme o ijo de máquinas insu icien e pa a el p ocesamien o de odos los abajos, maximiza el alo o al de los abajos ealizados. 128 2. Núme o de clases de máquinas y abajos 2.1 Una única clase de máquinas y abajos: Es el caso más sencillo del p oblema FSP. Cada abajo puede se p ocesado po cualquie máquina. Además, las máquinas es án disponible du an e odo el ho izon e empo al de plani icación. 2.2 Va ias clases de máquinas y abajos: En es e caso, cada abajo puede únicamen e se p ocesado po un subconjun o de máquinas. Es e escena io del p oblema posee dos 2 a ian es: 2.2.1 Shi Class Design: Se es ablecen un in e alo(shi ) en el que se encuen a disponible cada máquina, de o ma que cada máquina puede ealiza únicamen e abajos que se p ocesen den o de su in e alo. 2.2.2 License Class Design: Las máquinas es án disponibles du an e odo el ho izon e empo al. La compa ibilidad en e clases de abajos y máquinas se ige po mo i os écnicos. O os pa áme os que se dis inguen ambién en el p oblema son los siguien es: - El alo del abajo: El caso gene al es la asignación de un alo a cada abajo que mide el bene icio po comple a dicho abajo. A pesa de ello, en ocasiones se asigna el mismo alo a odos los abajos, o lo que es lo mismo, el alo de cada abajo es la unidad. - La p opiedad de in e umpi (p eemp ion) el p ocesamien o del abajo en una máquina: Aunque las ca ac e ís icas del p oblema obligan a que no exis an pausas en el p ocesamien o de un abajo, pues o que el iempo de p oceso coincide con el in e alo de p ocesamien o, el caso de p eemp ion se plan ea en algunos escena ios en los que se conside a admisible que el abajo puede se p ocesado po más de una máquina (el abajo puede sal a de una máquina a o a). En los siguien es capí ulos se desc iben los di e en es abajos ealizados en cada uno de las di e en es clases de p oblemas FSP comen adas, según obje i os y ipo de máquinas y abajos. 3. Una sola clase de abajo y de máquina Es la e sión más simple del p oblema FSP. Sob e dicha e sión se han aplicado los es obje i os mencionados en la sección 2. Con una sola clase de máquina y de abajo, los obje i os 1.1 y 1.2 son equi alen es, po lo que se desc iben como uno en lo que sigue. 3.1. Minimiza el núme o de máquinas Puede se és e el escena io que dio nomb e al p oblema FSP. La solución del p oblema se ob iene como una consecuencia di ec a del eo ema de Dilwo h (Diwo h, 1950) sob e la descomposición de conjun os pa cialmen e o denados, donde se es ablece que en cualquie conjun o pa cialmen e o denado el núme o mínimo de cadenas disjun as que albe gan odos los elemen os es igual al núme o mayo de elemen os mu uamen e no elacionados en el conjun o. El p oblema ue conside ado en p ime luga po Danzing y Fulke son (1954), y pos e io men e po Gup a e al(1979) y Nakajima e al (1982), mos ando algo i mos de 129 esolución de o den O(n log n). Ge sbakh y S e n(1978) ambién de inen FSP como un caso pa icula del p oblema de Dilwo h y p oponen un algo i mo basado en la cons ucción secuencial de p og amas de abajo pa a máquinas has a ago a odos los abajos. La idea pa a el cálculo del mínimo núme o de máquinas es á basada en el cálculo del g ado de solapamien o de los abajos en el iempo. El g ado de solapamien o de los abajos en un ins an e del ho izon e de plani icación se de ine como el núme o de abajos que se p ocesan du an e el ins an e . La exp esión co esponde con L = |{Ji / si ≤ < i}|. El núme o mínimo de máquinas co esponde ía con el mayo alo del g ado de solapamien o en algún ins an e . El mayo g ado de solapamien o se de ine como L = max{L / 0 ≤ ≤ T}, siendo [0,T] el ho izon e en el que se p oduce la ejecución de odos los abajos. Como una a ian e a la o mulación gene al del p oblema FSP en es e escena io, Fishe i e al (1987, 1989, 1992) plan ean el p oblema añadiendo es icciones de Sp ead-Time (lími e sob e el iempo que anscu e desde que se inicia la ac i idad de la máquina) y Wo king-Time (lími e en el iempo de ac i idad de cada máquina). 3.2. Maximiza el alo o al de los abajos ealizados En el caso en el que el núme o mínimo de máquinas necesa io pa a p ocesa odos los abajos es mayo al núme o de máquinas disponibles en el p oblema, es necesa io disc imina en e los abajos que pueden se ealizados. El p oblema FSP con es e obje i o puede se o mulado en é minos del p oblema de colo eado de g a os (Golumbi, 1980). A pesa de se és a una o ma iable de plan ea el p oblema, la o ma más e icien e de esol e lo es plan ea lo como un p oblema de lujo a cos e mínimo. Po an o, el p oblema es esoluble en iempo polinomial median e un algo i mo de lujo a cos e mínimo. En e las cons ucciones de g a os di igidos des acan la p opues a po A kin y Sil e be g (1987) basada en un cálculo de cliques según un g a o an e io con un nodo po cada abajo, y en el que un a co ep esen a el solapamien o en e los abajos de cada nodo. A pa i del cálculo de los cliques máximos de es e g a o, se cons uye un segundo g a o sob e el que si es posible aplica un algo i mo de lujo a cos e mínimo pa a de e mina los abajos a ealiza . En es e segundo g a o exis e un nodo po cada clique más un nodo inal. Po cada abajo exis e un a co desde el p ime nodo-clique al que pe enece has a el nodo-clique siguien e a su inalización. El cos e de cada a co es –wi y la capacidad igual a uno. Además, exis en a cos con in ini a capacidad y cos e nulo que unen los cliques consecu i os según o den c onológico. K oon e al (1995) de inen una cons ucción más di ec a que la an e io , en la que los nodos ep esen an los ins an es de comienzo y inalización de cada uno de los abajos. Los nodos o denados c onológicamen e se unen po a cos de capacidad in ini a y cos e nulo, además de un a co po cada abajo con capacidad uno y cos e –wi. Plan ean incluso un sencillo p ocedimien o de educción del g a o con obje o de disminui la dimensión del mismo en los casos en los que los abajos se encuen en muy dispe sos en el iempo. Ga cia e al (1999) p oponen una a ian e al g a o de K oon e al(1995), que es cons uido igualmen e de o ma di ec a, y que educe el núme o de nodos del p oblema. En dicho g a o exis e un nodo po cada abajo, mas un nodo inal. Exis e a cos que unen nodos consecu i os, de o ma semejan e a los g a os an e io es y un a co, po cada abajo Ji, desde su nodo has a 130 el nodo que ep esen a el p ime abajo que comienza as la inalización de Ji. La capacidad y el cos e se asignan de o ma semejan e a los g a os an e io es. En odos los casos, el lujo inicial en el nodo de pa ida co esponde con el núme o de máquinas del p oblema. En la Figu a 2 se p esen an los es g a os pa a el ejemplo ep esen ado en la Figu a 1. J3 J2 J1 J4 J5 iempo 0 1 2 ... T Figu a 1. Ejemplo con 5 abajos Nodo 1 = Clique {J1,J2,J3} Nodo 2 = Clique {J2,J3,J4} Nodo 3 = Clique {J3,J5} 1234 -w1 -w2 -w3 -w5 -w4 -m m A kin y Sil e be g 1 2 3 4 5 6 7 8 9 10 -w1 -w2 -w3 -w4-w5 -m 1234 -w1 -w2 -w3 -w5 -w4 5 6 -m K oon e al Ga cía e al Figu a 2. G a os de A kin y Sil e be g, K oon e al y Ga cia e al 4. Va ias clases de abajos y máquinas Se ía és e el caso más complejo del p oblema FSP. Aho a un abajo no puede se p ocesado po cualquie máquina. El caso de a ias clases de máquinas y abajos in eg a las dos a ian es señaladas en la clasi icación ealizada en la sección 2. Ambas a ian es p esen an las mismas ca ac e ís icas espec o a su complejidad. A pesa de ello, han sido analizados en la bibliog a ía de o ma independien e. A con inuación se desc iben cada una de ellas. 4.1. Shi Class Scheduling P oblem (SCSP) Kolen y K oon (1993) es udian la complejidad del p oblema a endiendo al obje i o que se de ina pa a el p oblema. De inen un único in e alo pa a cada máquina, asumiendo que dicha máquina puede únicamen e p ocesa abajos que se p ocesen po comple o den o su in e alo(shi ). P esen an dos de los obje i os comen ados del p oblema FSP, a e igua si, dado un conjun o de abajos y máquinas, es posible ealiza odos los abajos (SCS), y el máximo alo o al de abajos p ocesados sob e un conjun o de máquinas (MSCS). La complejidad de SCS y MSCS se de ine según el ipo de in e alo S de inido pa a los abajos. Pa a ello, de inen un g a o no di igido G(S) con la siguien e es uc u a: 131 - Un nodo po cada in e alo - Un a co en e cada dos in e alos que se solapen y que posean ins an es de inicio y in di e en es. Los esul ados que p ueban son los siguien es: - Si G(S) es á o mado únicamen e po nodos aislados, en onces MSCS es esoluble en iempo polinomial. - Si G(S) es un g a o bipa i o, en onces SCS es esoluble en iempo polinomial. - Si el máximo g ado de solapamien o de los in e alos es meno o igual a 2, en onces SCS es esoluble en iempo polinomial. - En el es o de casos SCS es NP-Comple o y MSCS es NP-Du o. Kolen y K oon (1994) p esen a un es udio de la complejidad del p oblema SCSP pa a el p ime o de los obje i os del p oblema. Es deci , asume un cos e pa a cada máquina y busca el conjun o de máquinas con cos e mínimo capaces de p ocesa odos los abajos. Es ablece una conside ación espec o a los cos es de las máquinas y di ide el es udio en dos casos: - Cos es uni o mes: El cos e de cada máquina es independien e (SCSCU) - Cos es dependien es del in e alo: El cos e depende del in e alo, no de la máquina. Dos máquinas con el mismo in e alo poseen el mismo cos e (SCSCD). Pa a el es udio de complejidad conside a el concep o de in e alos no dominados. Un in e alo [a,b] es no dominado cuando no exis e ningún in e alo [c,d] al que c ≤ a < b ≤ d. Los esul ados son análogos a los ob enidos pa a SCS y se esumen a con inuación: - SCSCU es esoluble en iempo polinomial si el mayo g ado de solapamien o de los in e alos no dominados es meno o igual a 2. En el es o de los casos es NP-Du o. - SCSCD puede se esuel o en iempo polinomial en los mismos casos que SCS. Pa a ambos p oblemas conside a el caso en el que puedan ompe se los abajos (p eemp i e), mos ando que dicha a ian e puede se esuel a en iempo polinomial median e un p oblema de lujo a cos e mínimo. Cuando el peso de los abajos es el mismo o, simplemen e, la unidad, y el obje i o es maximiza el núme o de abajos ealizados, el p oblema FSP con in e alos pa a máquinas apa ece ambién en la li e a u a como k-T ack Assignmen P oblem (TAP). Cu iosamen e, el es o de ca ac e ís icas coincide con las exp esadas pa a el p oblema MSCS. TAP es conside ado po B ucke y No dmann (1994) donde p oponen un mé odo exac o de esolución de o den O(nmk!mm). El mé odo cons uye un g a o que ecoge odos los posibles p og amas admisibles del p oblema. La u a máxima en el g a o ob iene la solución óp ima del p oblema. El mé odo se mues a muy ine icien e con un núme o de máquinas supe io a 4. Pa a un caso pa icula del p oblema p esen a un algo i mo de o den O(nm-1) basado ambién en el calculo de la u a máxima. Conside a ambién el caso en el que únicamen e exis en dos in e alos dis in os de abajo pa a las máquinas, p oponiendo un algo i mo de o den O(n). Es e caso es con emplado ambién po Hsu y Tsai (1989). Faigle and Nawijin (1995) y Faigle e al (1999) es udian ambién el p oblema TPU an o en su o ma no mal como en una e sión online. 132 4.2. License Class Scheduling P oblem (LCDP) LCDP es la e sión más gene al del p oblema FSP. Aquí la compa ibilidad en e máquinas y abajos se es ablece po mo i os écnicos y, gene almen e, la compa ibilidad se exp esa median e el é mino “ ene licencia”. El p oblema SCSP puede se exp esado como un caso pa icula del p oblema LCDP. Po ello, los mé odos de esolución pa a LCDP pueden se aplicados al p oblema SCSP. Kolen y K oon (1991) (1992) p esen an el es udio de la complejidad de es e p oblema. El es udio se ealiza de o ma simila al ealizado pa a el p oblema SCSP. Denominando LCD al p oblema de de e mina si, dado un conjun o de máquinas, es posible p ocesa odos los abajos, MLCD al p oblema de maximiza el alo de los abajos ealizados con un núme o de e minado de máquinas y, LCDC al p oblema de calcula el cos e o al mínimo necesa io pa a p ocesa odos los abajos, las conclusiones sob e la complejidad compu acional del p oblema son: - LCD es NP-Comple o pa a p oblemas con al menos 3 clases di e en es de máquinas. - MLCD es NP-Du o con al menos 2 clases di e en es de máquinas. - LCDC es NP-Du o con al menos 3 clases di e en es de máquinas. An e io men e, A kin y Sil e be g (1987) mues a que LCD es NP-Comple o cuando cada abajo puede se p ocesado po al menos 3 máquinas. A pesa de es os esul ados, p esen a un algo i mo exac o de o den O(nm+1) , basado en la cons ucción de un g a o de es ados admisibles. La aplicabilidad de es e algo i mo se educe a casos con un núme o muy educidos de máquinas. El p oblema LCD con dos clases máquinas ha sido a ado po Donde i y Emmons (1992), mos ando su complejidad polinomial. Ap oximaciones heu ís icas pa a MLCD han sido conside adas en Gab el (1995) y K oon e al (1995). En el p ime caso, el p oblema FSP es modelado como un p oblema de máximo conjun o de nodos independien es. Se analizan es ocedimien os heu ís icos pa a su esolución. El algo i mo que p esen a K oon e al(1995) es á basado en la esolución de algo i mos de lujo a cos e a mínimo sob e g a os cons uidos de o ma análoga a la desc i a en la sección 3.2. Va calculando co as supe io es e in e io es del p oblema has a un núme o máximo de i e aciones o una co a de la di e encia. El p oblema LCD, pe mi iendo o u a de abajos es conside ado en Donde i y Emmons (1993) p obando que puede se esuel o en iempo polinomial ans o mando el p oblema en un g a o de anspo e. Jansen (1994) conside a una gene alización de SCS y LCD, conside ando cos es pa a las máquinas. P opone una ap oximación algo í mica que asigna un abajo a una máquina en cada i e ación, pe o no ealiza expe imen os compu acionales. 133 5. Aplicaciones p ác icas del p oblema P oblemas p ác icos que implican la esolución de ins ancias del p oblema FSP apa ecen en múl iples á eas pe enecien es a la op imización de ecu sos. Las más impo an es que han sido es udiadas han sido: - P ocesos de man enimien o de a iones en ae opue os median e la asignación de ingenie os a a eas: Kolen y K oon (1991)(1992)(1993)(1994); Janson (1994) - Asignación de pue as a uelos en ae opue os con obje o de educi el núme o de uelos cuyos pasaje os son anspo ados a la e minal en bus: K oon e al (1991) - Plani icación de la cap u a de imágenes desde sa éli e: Gab el (1995) - Asignación de conduc o es en líneas de au obuses: Fishe i e al (1992) El p oblema de la asignación de aulas de clase (Ca e , 1989) es un p oblema bas an e p óximo a FSP, aunque no posee exac amen e las mismas ca ac e ís icas. También puede se aplicado al con ol del á ico aé eo, la plani icación de salas de ope aciones en hospi ales o la asignación de habi aciones en ho eles, en e o os. Re e encias A kin, E.M., and Sil e be g, E.L (1987) Scheduling jobs wi h ixed s a ing and inishing imes. Disc e e Applied Ma hema ics 18, pp. 1-8. B ucke , P. and No dmann, L. (1994). The k-T ack Assignmen P oblem. Compu ing, 52, pp. 97-122. Ca e , M.W. (1989). A lag angean elaxa ion app oach o he class oom assignmen p oblem, INFOR 27, 230-246. Dan zig G.B. and Fulke son, D.R. (1954). Minimizing he numbe o anke s o mee a ixed schedule. Na al Res. Logis . Qua . 1, pp. 217-222. Dilwo h R.P. (1950). A descomposi ion heo em o pa ially o de ed se s. Annals Ma hema ics, 51, pp. 161-166. Donde i, V., and Emmons, H. (1992). In e al scheduling wi h p ocesso s o wo ypes. Ope a ions Resea ch, 40, pp. 76-85. Donde i, V.R., and Emmons, H. (1993). Algo i hms o p eemp i e scheduling o di e en classes o p ocesso s o do jobs wi h ixed imes. Eu opean Jou nal o Ope a ional Resea ch, 70, pp. 316-326. Faigle, U., and Nawijn, W. M. (1995). No e on scheduling in e als on-line. Disc e e Applied Ma hema ics 58, pp. 13-17. Faigle, U., Ke n, W. and Nawijn, M. (1999). A G eedy On-Line Algo i hm o he k-T ack Assignmen P oblem. Jou nal o Algo i hms 31, pp. 196-210. Fische i, M., Ma ello, S. and To h, P. (1987). The ixed job schedule p oblem wi h sp ead ime cons ain s. Ope a ions Resea ch, 6, pp. 849-858. Fische i, M., Ma ello, S. and To h, P. (1989). The ixed job schedule p oblem wi h wo king ime cons ain s. Ope a ions Resea ch, 3, pp. 395-403. Fische i, M., Ma ello, S. and To h, P. (1992). App oxima ion algo i hms o ixed job schedule p oblems. Ope a ions Resea ch, 40, pp. 96-108. Gab el, V. (1995). Scheduling job wi hin ime windows on iden ical pa allel machines: New model and algo i hms. Eu opean Jou nal o Ope acional Resea ch, 83, pp. 320-329. 134 Ga cía, J.M., Lozano, S., Gue e o, F., Calle, M. and Smi h, K. (2001). P oduc ion and ehicle scheduling o eady-mix ope a ions. P oceedings o he 29 h In e na ional Con e ence on Compu e s & Indus ial Enginee ing (Oli ie , C.Gha bi, A. eds.) pp. 70-76. Ge sbakh I. and S e n H. (1978). Minimal Resou ces o Fixed and Va iable Job Schedules. Ope a ions Resea ch, 26 (1), pp. 68-85. Golumbi, M.C. (1980). Algo i hmic G aph Theo y and Pe ec G aphs. Academic P ess, New Yo k. Gup a, U.L., Lee, D.T., and Leung, J.Y.T (1979). An op imal solu ion o he channel assignmen p oblem. IEEE T ans. Comp. 28, pp. 807-810. Hsu, M. L. and Tsai K.H. (1989). A linea ime algo i hm o he wo- ack assignmen p oblem. P oceedings o he 27 h Alle on Con e ence on Communica ion, Con ols and Compu ing, pp. 291-300. Kolen, A.W.J., and K oon, L.G. (1991). On he compu a ional complexi y o (maximum) class scheduling. Eu opean Jou nal o Ope a ional Resea ch, 54, pp. 23-38. Kolen, A.W.J., and K oon, L.G. (1992). License class design: complexi y and algo i hms. Eu opean Jou nal o Ope acional Resea ch, 63, pp. 432-444. Kolen, A.W.J., and K oon, L.G. (1993). On he compu a ional complexi y o (Maximum) Shi Class Scheduling. Eu opean Jou nal o Ope acional Resea ch, 64, pp. 138-151. Kolen, A.W.J., and K oon, L.G. (1994). An analysis o shi class design p oblems. Eu opean Jou nal o Ope acional Resea ch, 79, pp. 417-430. K oon L.G., Salomon M. and Van Wassenho e L. N. (1995). Exac and app oxima ion algo i hms o he ope a ional ixed in e al scheduling p oblem. Eu opean Jou nal o Ope a ional Resea ch, 82, 190-205 Jansen, K., (1994). An app oxima ion algo i hm o he license and shi class design p oblem. Eu opean Jou nal o Ope a ional Resea ch, 73, pp. 127-131. Nakajima, K., Hakimi, S.L. and Lens a, J.K. (1982). Complexi y esul s o scheduling asks in Fixed In e als on wo ypes o machines. SIAM J. Compu , 11, pp. 512-520. 135