C. Necessaire and O. Suffisante-d, MALITE LOCALE On peut obtenir une condition nécessaire et suffisante grâce à une nouvelle mesure de priorité de chaque tâche que nous appelons pp1'p (re)

, Définition35 Nous définissons PRTF(i,Â) comme une fonction de la tâche i à l,instant  par PRTF(i,^)=2R(i,^)+pi=R(i,Â)+o

, de 2 fois la date d'exécution au plus tôt et de la durée ou encore la somme de la date d'exécution au plus tôt et de la date de fin au plus tôt. c'est une fonction continue linéaire par morceaux

, Nous considérons deux cas. 1o R(w,0w)<R(y

. Dans-ce-cas,

, On a deux sous-cas à envisager: 1.1o w=x Dans ce cas R(w,Q*)=fi,(x,0*) 1.2o w*x Dans ce cas on a we A*, ce qui implique R(w,Q*)>O(x,0*)=R(x,Q*)+p*>R(x

, Dans les deux sous-cas, on a obtenu: R(w,0w)>R(x,0*)

. Avec, 12) on obtient alors rr>R(x,g;6) qui implique: R(x,0*)<R(y

R. Ceci-contredit-l-'hypothèse, R(y,0*) 2o R(x,0w)>R(y,0*) et 2R(x,0w)+p, p.2

. Dans-ce-cas, on a la relation suivante pw(Py Ceci contredit l'hypothèse: Py<Pi, Vie Av(x)-{y}

, Dans tous les cas, il n'y a aucune tâche x vérifiant les conditions annoncées dans la propriété 3

Q. E. ,

, Cette propriété montre qu'un ordonnancement F-actif vérifre le théorème 3

, sauf dans le cas où il existe une tâche zeN-(Su(y)) telte euê py=pz

. Dans, &. Dessouky, and . Deogun, , 1981.

P. Dans-la,

, Les algorithmes PRTF et APRTF peuvent être utilisés pour déterminer une borure solution initiale

, Le minorant peut être calculé à partir de la règle de priorité SRPT en considérant le problème relaxé comportant des tâches internrptibles

, Le test d'optimalité peut être fait pendant le calcul du minorant

, Nous décrivons maintenant en détail la PSE

, Comme pour la minimisation de la somme des retards, I'algorithme est composé de trois phases: initialisation, séparation et terminaison. Les phases d'initialisation et de terminaison sont similaires à celle de la PSE pour la somme des retards. Nous expliquons uniquement la partie "séparation

, Création éventuelle d'un naeud B(h) li

. Etapel, éliminer B(h)li lorsqu'il ne peut pas conduire è u.n ordonnance m.ent actif' S'il existe une autre tâche je A(h) telle que O(i,t(h))<R(i't(h)) alors aller à l'étape 10' finsi

E. , Test 2 "éliminer Bh)li lorsqu'il ne peut po,s conduire à un ordonnancemcnt F' actif

, h))>l et R(x,0x)>R(i,0*) et PRTF(x,0x)>PRTF(i,Sx), où x est la dernière tâche ordorurancée dans B(h) alors aller à l'étape 10

. Etapes, éliminer B(h)li lorsqu'il est dorniné par une autre séquence B(h)lj d'après le théoÈm,e 3.73" S'il existe rure autre tâche je A(h) telle que O(i,t(h))sO(i,t(h)) et o0,(h)Fo(i,(h))s(r1-n)

E. , élirnincr B(h)li lorsqu'i| est dominé par unc outre séqu'ence Bh))j d'après le théoÈmB 3.74" S étant un ordonnancement composé de B(h) suivi des tâe;hes de A(h) dans I'ordre de leurs durées opératoires, s'il existe une autre tâche je A(h)

, Etape, vol.6

, Etape, vol.7

, Etape, vol.8

, -t(h)>Ir-r-Icard(B(h)) et q<pi et R(i,t(h))sR(i,t(h)) alors aller à l'étape f0

, élirnircr B(h)]i lorsqu'il est dominé por urae autre séqucrrce B(h)lj d'après le théorème 9.15" S'il existe une autre tâche je A(h) telle que O(i,t(h))>O(i,t(h)) et, Test, vol.5

, h)) alors aller à I'étape 10, ftnslCréer un nouueau naeud o correspondant ù l'ordannanaempnt partiel B(h) li" B(o):=B(h) li; t(o):=O(i,t(h)

, A(o):=A(h)-(i)

. Un and . Et-en-tirer-les-conséquences, Si card(A(o))s2 alors Construire I'ordonnancement o des tâches de A(o) à partir de I'instant t(o) en appliquant I'algorithme pRTF. cet ordonnancement local est optimal d'après le théorème B.g. si F(o)+F(o)<uB alors "nous auons obtenu un ord,onnancement complet strictement meilleur que |ordonnancement antérieur réalisabl.e.S", IIB est réinitialisé à F(o)+F(o), S devient B(o) suivi de o. Eliminer tout naeud o'de L telle que LB(o'>IIB, finsi, aller à l'étape tQ finsi A(o)), calculer un rninorant pour o et en tirer les conséquences" LB(o) :=.F(o) + MINOR(t(o)

. Minor, A(o)) est une fonction similaire à la fonction décrite dans la PSE pour la somme des retards. Il suffit d'y remplacer I'instruction MINOR:=MINOR+nax(t-Dj,0) par l'instruction MINOR, p.1

, Test 6 "ëliminer o lorsqu'il ne peut pas cond,uire ù un ordonnancement dont la sornrne des ternps de présenee est strictement inféricure à W\ Si LB(oÈIJB alors aller à t'étape 10

A. S. Potts-c, Dynamic programming state.space relaxaeion for single-machine scheduling, J. OpI. Res. Sac, vol.39, pp.4-152, 1988.

A. J. and F. Y. Chin, Scheduling the open shop o minimize mean flow time, SIAM J. Comput, vol.ll, pp.7-72, 1982.

A. J. Balas-e and Z. D. , The shifting bottleneck procedure for job shop scheduling, Man. 9ci, vol.34, p.391401, 1988.

B. U. and C. Y. Sullmn-r, Minimizing absolute and square deviation of completion times with different earliness and tardiness penalities and a common due date, Nav. Res. Logist, pp.739-751, 1987.

B. U. Ahmadi-r, An improved lower bound for minimizing weighted completion iimes with deadlines, Opns. Res, vol.35, pp.3-313, 1987.

B. P. Chakravarti-n, O,ptimal m-stâge production schedule, J. Can. Oprs. Res. Soc, vol.6, pp.7-78, 1968.

S. Coffman and J. E. Rjvest-ri, Orthogonal packing in two dimensions, SIAM. J. Comput, vol.9, pp.846-855, 1980.

B. Kr, In troductiorn to seqrencing and scludulinS, 1974.

B. K. and B. J. , A dynamic priority rule for scheduling against due-dates, J. o/ Opns. Man, vol.3, p.3742, 1982.

B. K. and N. H. , sequencing independent jobs with a single resource, Nav. Res. Lo gis t. Quart, vol.27, pp.499-510, 1980.

B. Kr and S. Z. , Sequencing with due-dates and early start times to minimize maxirnum târdiness, Nav. Res. Logkt. Quart, vol.2, pp.17-17, 1974.

J. Balzetnhcz, C. \v, and \. J. Slowinski-r, Scheduling under resource constraints -deterministic ttrodcls, J.C. BALTaeR, 1986.

B. Jr and G. B. I{gmahon, scheduling the general job-shop, Maz. Sci, vol.31, pp.5-598, 1985.

B. E. and P. Voyiatzis-k, Artificial memory in production management, R4eortde Recherche, vol.336, 1984.

B. G. Bensaè, . E. Ia, and . Dubois-d, Un systàne dodonnancement prévisionnel d'aaelier utilisant des connaissances théoriques et pratiques, Proceeding & Sixiùrus townées Interratiotules "Lcs Systènaes Eryerts et lews Applicuiors, pp.757-770, 1986.

B. R. , The thecy of dynamic programming, Bull.Amcr. Math..Soc, vol.60, pp.503-515, 1954.

B. E. and B. G. Dubois-d, OPAL: a knowledge-based system for industrial job-'shop scbeduling, NATO ÂSI $crics, 1988.

B. J. Watig-p, TVedimensional finiae bin-packing algorithms, I.Oper. Rcs. Sac, vol.38, pp.4-429, 1987.

B. L. and R. S. , Scheduling of a single machine to minimize ûoral weighaed completion time subject to release dates, Nay. Res. Lagist. Quart, vol.zg, pp.15-167, 1982.

B. E. , An application of the micro o product desrgn and d.isrriburion, J. Opns. Res. Soc, vol.33, issue.8, pp.271-280, 1932.

B. D. Marriott-m, A comparative evaluation for conoainer l@ding, 1987.

B. F. and P. , Application de règles de gestion à un système de fabrication: classification des ob|aetifs ameints en we de leur utilisation, p.372, 1985.

B. F. and P. , Analyse discriminanae: méthode du tlpe plus proches voisins urilisant un prétraiaement des données, 1985.

B. P. , F. M. , and P. Robillard, On scheduling with earliest stârt and due daaes with application to computing bounds for the (rr'mAEAEmax) problem, Nart Res. Logist. Qttut, vol.2, p.5747, 1973.

C. J. , Ordonnancement à contraintes disjonctives, pp.333-351, 1978.

C. J. , The one machine sequencing problem, Europ. J. Oper. Res, vol.ll, p.4247, 1982.

C. J. , Problènaes d'ordowancement à contraktes de ressources: algorithtttcs et complexité, Thèse d'état, p.mu

C. J. Pinson-e, An algorithm for solving the job-shop problem, Man. ici, vol.35, p.176, 1989.

C. S. Schneeberger-h, A note on the single machine scheduling problem with minimum weighaed completion time and maximum allowable tardinessn, Nav. Res.lngist. Quart, vol.33, pp.551-557, 1986.

C. R. Chretienne, On rylAE dynamic deaerministic systems Lcs réseaux de Peti temportsésMinimisation de la somme des retards pour les problèmes d'qdonnancernent à une machine, Thèse d'état, pp.537-541, 1979.

C. C. Portmann-m, Some new efficient methods to solve the nlUr;l}Ti scheduling problem b), "single machine scheduling prroblems with release dates, Europ.I. Oper. Res, p.1232, 1990.

C. C. Fortmann-m, W. Of, C. Iurl, C. G. Jr-e, T. L. Fi-/-q et al., Single machine scheduling prroblenrs witi release dat?sMinimizing expected makespan on uniform processor systemsPerformance bounds for level-ciented wo-dimensional packing algorithms, Proceeding SIAI|.I Comput.,g, pp.2-25177, 1980.

C. R. Lv, . Maxmll-lv-l, and . !. Miller-l, Tlwory g schcduling, 1967.

C. S. , The complexity of theorem-proving procedures, Proc. 3rd Ann. ACM Synp. on Tlrcory of Computing, Association fa Computing lvlaehinery, pp.5-158, 1971.

D. J. , On scheduling with ready times to minimize mean flow time, The Comp. J, pp.320-328, 1983.

D. M. and D. J. , Sequencing jobs with unequal ready times to minimize mean flow time, SIAM J. Comput, vol.10, pp.192-202, 1981.

D. M. Margenthaler-cr, The one-machine sequencing problem with early starts and due Mtss, AI I E Transactions, vol.4, pp.214-222, 1972.

D. and .. B. , Computational consideration in packing algorithm development, 1987.

D. J. Leung-j and -. F. Teuton-jr-o, Minimizing otal tardiness on one machine is NP-hardDevelopment of m-stage decision rule for scheduling n jobs through m-machines, Math. Oper. Re.ç. O pns. Res, vol.13, pp.47-1497, 1965.

E. W. Even-s and . M. Isaacs-i, Bounds for the optimal scheduling of n jobs on m processors, M an. Sci, pp.268-279, 1964.

E. H. , One-machine sequencing lo minimize certain functions of job tardiness, Opzs. Res, vol.17, pp.701-715

E. H. , Scheduling to a common due daae on parallel uniform processors, Nav. Res. Logist, vol.34, pp.803-810, 1987.

E. J. Novembre, E. J. Fontan-g, and . Merce-c, Atulyse sorc contraintes et aide à la deckion pour certains problèmcs d'ordonnancemcnt, thèse d'étatUn nouveau concept de dominance pour I'ordonnancement de travaux sur une machine, pp.15-26, 1976.

E. J. Fontan-g and R. F. Merce-c, A new dominance concept on a single machine with ready times and due dates, Opns. Res, vol.3, pp.4-127, 1983.

F. M. , A dual algorithm for the one-machine scheduling problem, Math. Prog, vol.11, pp.229-251, 1976.

F. M. Krieger-a, Analysis of a linearization heuristc for single machine scheduling to maximize profit, pp.218-225, 1984.

F. M. Lageweg-8, L. J. , and R. H. Kan-a, Surrogate duality relaxation for the job shop scheduling, Ddscr. Appl. Math, vol.5, pp.65-75, 1983.

F. M. , Constraint-directed search: a case study of job-shop scheduling, 1983.

F. M. and S. S. , ISIS: A knowledge based sysaem for factory scheduling, Expert System Iownal, p.2549, 1984.

G. M. and J. D. , Computers and intractability: a guide to tlrcory of NP-completeness, 1978.

G. M. and J. D. , Approximation algorithms for bin packing propblems, Analysis and Design of Algoritfuns in Combinatorial Optimization, 1981.

G. J. and R. D. , A heuristic for packing boxes into a con[ainer, Comput. and Opns. Res, issue.1, pp.147-156, 1980.

G. Jr and W. S. , Heuristics in job shop scheduling, Man. Sci, vol.13, pp.167-190, 1966.

G. F. , Surrogate constraint duality in mathernatical programm ing, Opns. Res, vol.23, p.434451, 1975.

G. T. Sanhi-s, Flowshop and jobshop schedules: complexity and approxim ation', Opns. Res, vol.26, pp.36-67, 1978.

G. J. No\tickie and Z. S. , A_bloc_k approach forsingle-machine scheduling with release dates and due dat?s, Europ. J. Oper. Res, vol.26, pp.279-284, 1986.

G. , S. J. Skubalska-e, and C. Smutmqki, On flow shop scheduling with release and due dates to minimize maximum latene,ss, I. Opl. Res. Soc, vol.34, pp.615-620, 1983.

G. E. Lawler-e, L. J. , and R. H. Kan-a, (lg7g), "Oprimizar.ion and approximation in deaerministic sequencing and scheduling: a survey, pp.7-326

G. J. Reddi and S. S. , Im_proved dominance conditions for the three-machine flowshop scheduling problem, Opns. Res, vol.26, pp.201-203, 1978.

G. S. and K. J. , single machine scheduling research, OMEGA Int.I. Man.,Sci, vol.15, pp.207-227, 1987.

H. N. 'riiee-w, Average and worst-case analysis of heuristics for the maximum rardiness problem, Europ. J. Oper. Res, vol.26, pp.272-277, 1986.

H. C. Knott-k and . J. Egbeli-]-p, A heuristic approach to the three-dimensional cargo-loading problem, Int. J. Prod. Res, vol.27, pp.757-774, 1989.

H. A. Porr_s and C. , An algorithm for single machine sequencing wirh release dates ro minimize toral weighted completion time, Dricr. Appt. Mùh, vol.5, pp.99-109, 1983.

I. N. , ADIRI t Ç?azl, "fn e$c_i91t-alg_orithm for the two-machines unit-timeirb-shop schedule-length problem, Math. of Oper. Res, vol.7, pp.334-337

H. H. , M-odéIisation et analyse des systèmes de producrion discrets par les réseaux de petri temryrisés, Thèse de doctuat, 1989.

J. J. , scheduling-a production line to minimize maximum tardiness, Research Report, vol.43, 1955.

J. J. , An extension of Johnson's results on jobJor scheduling, Nav. Res. Logist. ewrt, vol.3, pp.20-203, 1956.

J. , O,ptimal two-and three-stage production schedules witl setup times included, Nav. Res. Logist. Quart, pp.6-68, 1954.

J. C. , An economic evaluaûon of job shop dispatching rules, Man. 5ci, vol.20, pp.293-307, 1973.

K. T. , 9 Ft qpFality of static priority policies in srochasric scheduting on paralet machines, J. Appl. Prob, vol.24, p.43049, 1987.

K. Jj, Expert systems in production scheduling, Europ. J. oper. Res, vol.29, pp.51-59, 1986.

K. K. Kusiak, Manufacturing and artificial intelligenceArtificial intelligence and operations research in flexible manufacruring sysrems, Robotics INFOR, vol.25, issue.1, pp.3-5, 1985.

K. A. and C. M. , Expert systems for planning and scheduling manufacturing systems, Europ. J. Oper. Res, vol.34, pp.3-130, 1988.

L. Bj, L. J. , and R. H. Kan-a, Minimizing maximum lateness on one machine: computâtional experience and some applications, Statist. Neer, vol.30, p.2541, 1976.

L. 8. , L. J. , and R. H. Kan-a, Job-shop scheduling by implicit enumeration, M an. Sci, p.441450, 1977.

L. B. , L. J. , and R. H. Kan-a, A general bounding scheme for the permutation fl ow-shop problem, O p ns. Re s, vol.26, pp.53-67, 1978.

L. S. Lakshmanan-r and R. L. Papineau-r, Technical Note???Optimal Single-Machine Scheduling with Earliness and Tardiness Penalties, Operations Research, vol.26, issue.6, pp.1079-1082, 1978.
DOI : 10.1287/opre.26.6.1079

L. R. , D. M. Devor-r, and . L. Lawler-e, A fqward-baekward procedure for the single machine problem to minimize maximum latenessOn scheduling problems with deferral costs, Transactions Man. Sci, vol.17, pp.252-254, 1964.

L. E. , Optimal sequencing of a single machine subject to precedcnce constrainls, Man. Sci, vol.19, pp.544-546, 1973.

L. E. , A 'pseudopolynomial' algorithm for sequencing jobs o minimize total tardiness, Ann. of Disu. Math', vol.4, pp.331-342, 1977.

L. E. , Sequencing jobs to minimize total weighted completion time subject to precedcnce constraints, Ann. of Discr. Math, vol.2, pp.75-90, 1978.

L. E. , A fully polynomial approximation scheme for the total tardiness problem, Opns. Res. Letters, vol.1, pp.207-208, 1982.

L. , L. E. , and L. J. , On preemptive scheduling of unrelated parallel processors by linear programming, L of Ass. for Comput. Mach, vol.2, pp.612-619, 1978.

L. , L. E. , L. J. , R. H. Kan-a, and S. D. , Sequencing and scheduling: algorithms and complexity, Report BS-R8909 Center for Mathematics and Computer Science, 1989.

L. J. , R. H. Kan-a, and . Brucker-p, Complexity of machine scheduling problems, Ann. of Discr. Math, pp.343-362, 1977.

L. Pape and C. , SOJA: a daily working scheduling system, SOJA's system and inference engine, Proceeding of the 5th Technical Cor{erence of tlu Brilish Computer Society Specialist Group on Expert Sy s te ms, pp.195-197, 1985.

L. Pape and C. Sauve-b, SOJA: un système d'ordonnancement journalier d'atelier, Proceeding de Cinquièraes Journées Internationales "l*s Systènus Erperts et leurs Applications, pp.9-867, 1985.

L. P. Hoitomt-d, M. E. , and R. K. Eee, Parallel machine rcheduling using lagrangian relaxatton, p.24, 1988.

G. Mcmahon, Optimal prodrrction schedules for flow shops, Canad. Opns. Res. Soc. J, vol.7, pp.4-5, 1969.

G. Mcmahon and F. M. , On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness, Operations Research, vol.23, issue.3, pp.47-54, 1975.
DOI : 10.1287/opre.23.3.475

M. R. and R. V. Molet, A note on the weighted tardiness problem, Opns. Res, vol.35, pp.4-4521, 1987.

M. J. , Sequencing n jobs on one maehine o minimize the number of tardy jobs, Man. Sci, vol.15, pp.102-109, 1968.

M. J. Thompson-g, P. S. Ow, and T. E. Morton, Industial scludulingThe single machine early/tardy problem177-lgl PANV/ALKER s.s., ISKANDER wA survey of scheduling rules, Man. sci. opzs. Res, vol.32, pp.45-61, 1963.

P. H. and R. H. , Generation of knowledge about the conrrol of a flow shop using data-analysis oriented learning techniques and simulationGeneration of knowledge abour the conrrol of a flow shop using simulaton and a learning algorithm, Rapport de Recherche Computer Appticàtion in P roduc tb n and Engi ruering, 1988.

P. L8-sepaembre and P. M. , Méthodes de décomposition spatiale et temporelle en ordonnancement de Ia productionA sequencing problem witi release dates and clustered jobs, Thèse détat, pp.5-731, 1986.

P. C. Van-was_senhove-l, Analysis of heurisrics for sequencing jobs on one machine with release dates and delivery timasA decomposition algorithm for the singte machine lorâl tardiness problem, Opns. Res. Opns. Res. I*uers, vol.28, pp.1436-144, 1980.

P. C. Van-wassenhove-l, An algorithm for single machine sequencing with deadlines to minimize total weighted completion time, Europ. L Oper. Res, vol.12, pp.379-397, 1983.

P. C. Van-v-/-assenhove-l, A branch and bound algorithm for the total weighted tardiness problem, O pns. Res, vol.33, pp.363-377, 1985.

P. C. Van-wassenhove-l, Dynamic programming and decomposition approaches for the single machine totâl tffdiness problem, Europ. J. Oper. Res, vol.32, p.4, 1987.

P. , Q. J. , and R. H. Voyiatzis-k, Urilisation de I'intelligence artificielle dans un problème d'ordonnancement, Proceeding du Congrès Automatique: Productique et Robotiquc Intelligente novembre, pp.15-17, 1983.

P. , Q. J. , and R. H. Voyiatzis-k, Problème d'ordonnancemenu utilisation de l'intelligence artificielle, Lc Nouvel Automatisme, pp.59-62, 1983.

R. Kan, A. H. Nijhofl-the-hague, R. H. Kan-a, . J. Lage\ryeg-8, R. M. Lenstra et al., Machine sequencing problems: classification, complertry and cotnputationMinimizing totâl costs in one-machineAn analysis of heuristic trim-loss algorithms, O pns. Res. J.K, vol.2312, pp.908-92771, 1975.

R. B. , Algèbre modcrne et tMorie des graphes,DUNOD ROY 8Les problèmes d'ordonnancement avec contrainaes disjonctives, Notes DS no 9 bis, 1964.

S. S. , Algorit}ms for scheduling independent tâsks, J. of Ass.for Comput. Mach, vol.23, pp.116-127, 1976.

S. L. , A proof of the optimality of the shoraest remaining processing time discipline, Opns. Res, vol.16, pp.687-690, 1968.

S. L. Baker-k, Dynamic prograrnming solution of sequencing problems with precedence constraints, Opns. Res, vol.26, p.445449, 1978.

S. T. , A. L. , and G. P. , An algorithm for the single-machine sequencing problem to minimize total târdiness, llE Transactions, vol.15, pp.363-399, 1983.

S. , On the n-job, one-machine, sequence-independent scheduling problem with tardiness penalities: a branch-bound solution, Man. Sci, vol.8, pp.30-8313, 1972.

S. J. , Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs, O pns. Res, vol.23, pp.283-298, 1975.

S. D. , A new proof of the optimality of the shortest remaining processing time discipline, Opns. Res, vol.26, pp.197-199, 1978.

S. R. and D. R. , A general algorithm for solution of the n-job m-machine sequencing problem of the flow shop, Opns. Res, vol.15, pp.71-82, 1967.

S. and /. E. , Various optimizers for single-stage production, Ncv. Res. lngist. Quart, vol.3, pp.59-65, 1956.

S. V. , A hybrid algorithm for the one-machine sequencing problem to minimize total hrdiness", N av. R e s. Lo gist, Qwrt, vol.18, pp.317-327, 1971.

S. M. , A survey of artificial intelligence-based scheduling systems, Proceeding of Fall Industrial Engineering Conterence, p.395405, 1986.

S. P. and A. M. , Minimizing the sum of absolute lateness in single machine and multimachine scheduling, Nav. Res. Logkt. Quart, vol.3, pp.325-333, 1984.

S. W. , Elimination methods in the mxn sequencing problem, Nav. Res. Logisr. Quarr, vol.18, pp.295-305, 1971.

S. and A. W. , Optimal elimination methods in the mxn flow-shop scheduling problemDominance conditions for the three-machine flow-shop problem, Opns. Res. Opns. Res, vol.226, pp.1250-259, 1973.

S. /. , P. M. Lru, and J. , The single machine problem with a quadratic cost function of completion times, Man. $ci, vol.34, pp.1480-1488, 1988.

T. C. , Rescheduling o minimize makespan on a changing number of identical processors, N av. Res. Lo gist. Quart, vol.33, issue.7, pp.17-74, 1986.

W. To\rynsend, Sequencing n jobs on m machines to minimise maximum tardiness: a brarrch-and-bound solution, 1977.

V. A. Pj and M. T. , Priority rules for job shops with weighaed tardines costs, Man. Sci, vol.33, pp.1035-1035, 1987.

, Lae

V. K. , Utilisation de l'intelligence artilicielle pour les problèmes d'ordonnancemânt, 1987.

V. and A. P. , Two algorithms for constrained two-dimensional cutting stock problems, Opns. Res, vol.31, pp.573-586, 1982.

W. L. and I. J. , An improved algorithm for scheduling independent tasks, pp.239-245, 1971.

Y. M. , An approximaae solution of machine scheduling problems by decomposition melhod, Int.I. Prod. Res, vol.15, pp.59-608, 1977.

Z. S. and G. J. , An algorithm for single machine sequencing with release daaes ro minimize maximum cost, Disc. Appl. Math, vol.23, pp.73-89, 1989.

A. Annexe,

E. La-fonction and P. Est-donnée-par-la-forrrule, (i,A), dyl En étudiant les différents cas possibles et en supposant que I'on travaille sur les délais corrigés (di>ri+pi), on obtient immédiatement: PRTT(i,A)= ri+di si À<ri A+di si riSÂSdi-pi 2Â+pi si di-pi<^ C'est une fonction non décroissante

E. Croît-À-la-même-vitesse-que-a-tant-que-la-tâche-planifiée and . Au, plus tôt n'est pas en retard, et son ordonnée à I'origine eet d1. Aussi, si on compare sa priorité avec celle d'une autre tâche disponible et non en retard en conrmençant à I'instant Â, c'est la tâche de plus petit délai condgé qui est la plus prioritaire. Elle croît à une vitesse double de  lorsque la tâche planifiée au plus tôt est en retard et son ordonnée à I'origine est pi, Aussi, si on compare sa priorité avec celle d'une autre tâche qui serait aussi en retard en commençant en A, c'est la tâche de plus petite durée qui est la plus prioritaire

, lorsque l'on compare deux tâches à placer consécutivement sur une machine, passe de la règle FIFO (First In First Out) quand une des deux tâches n'est pas encore sur le point d'arriver, à la règle EDD (Earliest Due Date) quand aucune des deux tâches n'est en retard, puis à la règle SPT (Shortest Processing Time) lorsque les deux tâches sont en retard. Les cas transitoires (par exemple, I'une en retard et pas I'autre) sont traités également puisque PRTT, On peut considérer que cette règle de priorité est une règle souple qui

, Les instants où la priorité change peuvent être obtenus analytiquement dans chacun des cas possibles comme le

, Toutes les frgures ont été réalisées en supposant arbitrairement que la tâche d'indice i est la tâche ayant le plus petit délai (di<d;)

L. Fi, ri+diSr;+d; (ou encore d5-d;>ri-r;, c'est-à-dire que l'écart entre les délais est supérieur à l'écart entre les dates d'arrivées en inversant les tâches et quelle que soit la tâche qui arrive la première) Dans ce cas, la tâche de plus petit délai est toujours prioritaire si On construit alors un problème P" à partir du problème P' en

E. Vi,

E. Vi, q=[max(ho'err)+min(i,],)lD (sd'1 d'après

*. , <\ et Gi k=oeq+1 Oi =+ %iD- k=os**1

, =+ d'i>[ho. +min(i,I)

L. Dans-tous and . Cas,

B. Alors-en-utilisant-le-corollaire, 1 et (8.1?), on obtient

T. <t,

T. <t, oitsl) (8.22) (B.23)

, On construit un problème p(3) tr partir de P" en conser

, Op1a1) @.ùL)

, on peut facilement construire un ordonnancement optimal Oiral (voir la figure 8.2.c)Il suffit pour cela de mettre les tâches dans I'ordre EDD (Earliest Due Date) On place donc les tâches n'appartenant pas à E' dans I'ordre de leur numérotation, les unes derrière les autres, sans laisser la machine inoccupée

. En-fait and E. Cet-ordonnancement-vérifie, Vij, ie E', jG E', j>i: min(j,I)>min(i,I) et

, + max(ho' err)>max(ho' er

. Avec, 26) et (B.27), on a: Vij, ie E', jÉ E', j>i, + erràe' et \>hoi max(h6r,et5)+min6,X,)>max(hoi,?jr)*min(i,I) =+ d'j)

. Pour-finir-on-majore-t-(-p,

, Oi1sl

C. Vi, i=[i+min(À,i)]D fo si i

E. Tiho, E. Vi, and . Ctgf=li-ri, 3,or,r,r={Lt.t aI{-d,i,0)=maxli-ri-min(x,i)-max(ho'eti

. Ti, O;1s1)={i-max(hoi,eri)-max[i-ri,min(i,I)-max(ho'err),01]D =-max[-ri-min(i,À),max(holerl)-i1p =min[ti+min(i,I),i-max -max(hor-i,e"r-i )lD =min[ti+min(i,L),min(i-ho'i-e

E. Fait,