Mathematics - 356 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 Minimizing total Completion Time and Maximum late Work Simultaneously T. S. Abdul-Razaq and F. Sh. Fandi Department of Mathematics, College of Science , Al_Mustansiriya University Department of Mathematics, College of Education, for Pure Sciences, Al-Anbar university Received in: 1 April 2012 Accepted in: 22 April 2012 Abstract In this paper, the problem of scheduling jobs on one machine for a variety multicriteria are considered to minimize total completion time and maximum late work. A set of n independent jobs has to be scheduled on a single machine that is continuously available from time zero onwards and that can handle no more than one job at a time. Job i,(i=1,…,n) requires processing during a given positive uninterrupted time pi, and its due date di. For the bicriteria problems, some algorithms are proposed to find efficient (Pareto) solutions for simultaneous case. Also for the multicriteria problem we proposed general algorithms which gives efficient solutions within the efficient range. Keyword:- schedule, multicriteria, single machine, bicriteria. Introduction The problem of scheduling a set N={1,…..,n} of n jobs on a single machine to minimize a variety of multicriteria may be stated as follows. Each job i, (i=1,….,n) is to be processed on a single machine which can handle only one job at a time. Associ- -ated with job i its processing time pi and its due date di. All jobs are available for processing at time zero. A schedule σ=(1,…,n) specifies for each job when it is executed while observing the machine availability constraints and the schedule produce a completion time ci=Σpi for each job i, In this paper, for the first time. We use the late work object in multicriteria scheduling problem. Given a schedule σ, the late work vi(σ) for job i,(i=1,…,n) which is amount of processing performed on job i after its due date di, is easy compute. We abbreviate vi(σ) to vi for each job i, hence we have: (1) If vi=0, then job i is early with ci ≤ di. (2) If 0 < vi < pi, then job i is partially early. (3) If vi = pi, then job i is late with ci ≥ di + pi. This means that the late work for job i is given by vi= Notation and Basic Concepts: The following notation will be used in this paper: n = number of jobs. Pi = processing time of job i. di = due date of job i. ci = completion time of job i. Σci= the total completion times. Mathematics - 357 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 vi= the late work penalty for job i. Vmax= Max {vi}, the maximum late work. Li = lateness of job i, Li = ci - di. Ti = tardiness of job i, Ti = Max {ci - di ,0}. Lmax = Max{Li}, maximum lateness of all job in a schedule. Tmax = Max{Ti}, maximum tardiness of all job in a schedule. The cost fi for each job i, (i=1,…,n) usually takes on the variable ci. Common optimality criteria are usually in the form Σfi and fmax= Max{fi}. Theorem(1)(Jackson 1955)[1]. The 1// Tmax problem is minimized by sequencing the jobs according to the earliest-due- date (EDD) rule, that is, in order of non-decreasing di. ■ Theorem (2)(Smith 1956)[2]. The 1// problem is minimized by sequencing the jobs according to the shortest –processing-time (SPT) rule ,that is, in order of non-decreasing pi. ■ Theorem(3)(Lawler 1973)[3].The 1//fmax problem, fmax is minimized as follows: while there are unassigned jobs, assign the job that has minimum cost when scheduled in the last unassigned position in that position.■ Definition(1)[4]: A feasible schedule for a problem 1//Lex(f,g) is a schedule in which the primary criterion f is satisfied. Definition(2)[4]: An optimal schedule for 1//Lex(f,g) is a feasible schedule that minimizes the secondary criterion g. Definition(3):A feasible schedule σ* is Pareto optimal, or non-dominated(efficient), with respect to the performance criteria f and g if there is no feasible schedule π such that both f(π) ≤ f(σ*) and g(π)≤g(σ*), where at least one of the inequalities is strict. Definition(4)[5]: The function F(f,g) is said to be non-decreasing in both argument, if for any pair of outcome value (x,y) of the functions f and g, we have F(x,y) ≤ F( x+A , y+B) for each pair of non-negative value A and B. Theorem (4)[6]: If the composite objective function F(f,g) is non-decreasing in both argument, then there exists a Pareto optimal schedule that minimize F. Definition(5)[7]: The term ”optimize” in a multi-objective decision making problem refers to a solution around which there is no way of improving any objective without worsening at least one other objective. Definition (6)[8]: A point x = (x1, . . . , xk) is Pareto optimal within a given set S, if S does not contain any other point y=(y1, . . . , yk) with yi ≤ xi for i =1, . . . , k. Correspondingly, a schedule σ corresponds to a Pareto optimal point if there is no feasible schedule with ≤ for k=1, . . . , K, where at least one of the inequalities is strict; in this case, we say that σ is not dominated. Definition(7)[8]:hierarchical minimization: The performance criteria f1, . . . ,fk are indexed in order of decreasing importance. First, f1 is minimized. Next, f2 is minimized subject to the constraint that the schedule has minimal f1 value. If necessary, f3 is minimized subject to the constraint that the values for f1 and f2 are equal to the values determined in the previous step. Theorem(5)[9]: Consider the composite objective function F with F(π )= F(f1(π),…,fk(π)), where F is non- decreasing in all performance criteria fk. There is a Pareto optimal schedule with respect to f1,…,fk that minimizes the function F. fmax is Regular Measure : Now, we will consider the bicriteria that concerns the hierarchical and simultaneou s minimization of bicriteria regular cost function for jobs i, which means that fi(ci) does not decrease when ci increased. Hoogeveen and Van de Valde [10] proved that 1//F(Σci,fmax) Mathematics - 358 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 problem is solved in polynomial time, Van Wassenhove and Gelders [11] solved 1//F(Σci,Tmax) problem, Emmons [12] presented the hierarchical problem 1//Lex(fmax,Σci), where f*=Min{fmax} denotes the optimal solution value of the 1// fmax problem, which is solved in O(n2) time by Lawler algorithm[3]. Let fmax= Vmax in our study, since criterion Vma x is a particular case of the function fmax . Now, consider the following two problems: 1//Lex(Σci, Vmax) problem, and 1//Lex(Vmax, Σci ) problem. The 1//Lex(Σci,Vmax) problem (P1): This problem can be written as: Min Vmax s.t cσ(i) ≥ pσ(i) i=1,…,n. cσ(i) = cσ(i-1) + pσ(i) i=2,…,n. ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )         =≤+ =+<< =≤ = n 1,...,i , iσ c iσ p iσ d if iσ p n1,...,i , iσ pid iσ c iσ d if iσ d- iσ c n1,...,i , iσ d iσ c if 0 iσ v pσ(i) ≥ vσ(i) i=1,…,n. vσ(i) ≥ 0 i=1,…,n. Σci =∆, where ∆= Σci(SPT). It is clear that the SPT rule is feasible for problem(P1). Also the SPT rule is optimal for problem(P1) if there exist a tie (jobs with equal processing times) then order these jobs so that Vmax is minimum. The 1//Lex(Vmax, Σci) problem(P2): This problem can be written as: Min Σci s.t cσ(i) ≥ pσ(i) i=1,…,n. cσ(i) = cσ(i-1) + pσ(i) i=2,…,n. ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )         =≤+ =+<< =≤ = n 1,...,i , iσ c iσ p iσ d if iσ p n1,...,i , iσ pid iσ c iσ d if iσ d- iσ c n1,...,i , iσ d iσ c if 0 iσ v pσ(i) ≥ vσ(i) i=1,…,n. vσ(i) ≥ 0 i=1,…,n. Vmax= ∆, where ∆= Vmax(Lawler). Algorithm(1) for finding an optimal value for problem(P2): Mathematics - 359 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 Step(0): Compute Vmax by using (Lawler algorithm) and set σ= (φ). Step(1): Put ∆= Vmax(Lawler), N={1,…,n}, K=n, t=Cmax= Σpi . Step(2): Calculate vi, i N as follows:       =≤+ =+<< =≤ = n 1,...,i ,ic ipid if ip n1,...,i ,ipid ic id if id- ic n1,...,i ,id ic if 0 iv Step(3): Find a job j* N, such that 1.vj*≤ ∆. 2. pj*≥ pi , j*, i N and vi ≤ ∆. Then assign job j* in position K of σ =(σ(K), σ ). Step(4): Set t=t-pj*, N=N-{j*}, K=K-1, if K >1 go to step(2), otherwise go to step(5). Step(5): Calculate Σcσ(i) for the sequence jobs σ =(σ(1),…,σ(n)). Step(6): Stop. Proposition(1): Algorithm(1) gives an optimal solution of 1//Lex(Vmax, Σci) problem. Proof: Since the problem 1//Lex(Vmax, Σci) can be written as: Min Σci S.t vi ≤ Vmax (Lawler) i=1,…,n First notice that at each decision point the set of schedulable jobs is inspected (i.e. these jobs that can be scheduled without violating the maximum late work (Vmax(Lawler))(which is obtained by Lawler algorithm)), any job j* that is chosen in step (3) of algorithm(1) to be scheduled last. Second, if there exists a tie (more than one schedulable job i) then we choose the job j* with largest pj* to be schedule last which minimizes Σci also. Hence, any schedule constructed by algorithm(1) is optimal.■ Algorithm(1) is a general algorithm can be used for solving problems of the following forms: (1) 1//Lex(fmax, Σci), where fmax {Lmax, Tmax, Vmax, }. (2) 1//Lex(fmax, ), where fmax {Lmax, Tmax, Vmax, }. The 1//Lex( ,Tmax) problem(P3): This problem can be written as: Min Tmax s.t =∆, where ∆= (Lawler). Algorithm(2) for finding an optimal value for problem(P3): Mathematics - 360 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 Step(0): Compute =min{max{wivi}}, by using (Lawler algorithm). Step(1): Put ∆= (Lawler), N={1,…,n}, K=n, t=Cmax=Σpi and set σ= (φ). Step(2): Calculate wivi, i N as follows:       =≤+ =+<< =≤ = n 1,...,i ,ic ipid if ipiw n1,...,i ,ipid ic id if )id- i(ciw n1,...,i ,id ic if 0 iviw Step(3):Find a job j*∈N, such that 1. wj*vj*≤ ∆. 2. dj*≥ di , j*,i N and wivi ≤ ∆. Then assign job j* in position K of σ =(σ(K), σ ). Step(4): Set t=t-pj*, N =N-{j*}, K=K-1, if K >1 go to step(2), otherwise go to step(5). Step(5): Calculate Tmax(σ) for the sequence jobs σ =(σ(1),…,σ(n)). Step(6): Stop. Example(1): Consider the problem 1//Lex( , Tmax) with the following data: i 1 2 3 4 pi 3 1 2 4 di 4 6 1 2 wi 2 3 2 5 By applying Lawler,s algorithm (Step(0)) we get a schedule σ=(4,1,3,2) with =10 and Tmax=8. Put ∆=10. i 1 2 3 4 Job j* t=Cmax wivi 10 6 4 20 2 9 * 4 20 1 6 * * 20 3 4 * * * 4 Hence, we get optimal schedule σ = (4,3,1,2) with =10 and Tmax=5. 7. Minimizing Total Completion Time and Maximum late work. In this section we will try to find all efficient (Pareto optimal) solutions for 1//F(Σci, Vmax) problem which is denoted by problem(P4). 7.1 The 1//F(Vmax, Σci) problem(P4): The 1//F(Σci, Vmax) problem can be written as: Min Σci s.t. Vmax ≤ ∆, where ∆ [Vmax(Lawler) , Vmax(SPT)]. It is clear that the 1//F(Σci, Vmax) problem originates from 1// Σci problem and 1//Vma x problem, both problems are solvable in O(n log n) time. In order to find the set of Pareto optimal points, we solve the problem of minimizing Σci subject to Vmax≤ ∆, where ∆ corresponds to the Vmax value of a Pareto optimal point. Mathematics - 361 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 Algorithm(3) for finding a set of all efficient solutions for problem(P4): Step(0): Put ∆= Σpi, N={1,...,n}, K=n, t=Cmax=Σpi and set σ = (φ). Step(1): Calculate vi, i N as follows:       =≤+ =+<< =≤ = n 1,...,i ,ic ipid if ip n1,...,i ,ipid ic id if id- ic n1,...,i ,id ic if 0 iv Step(2): Find a job j* N, such that 1.vj*≤ ∆. 2. pj* > pi, j*, i N and vi ≤ ∆, if pj*= pi choose the job with smallest vj*. Then assign job j* in position K of σ =(σ(K), σ ). If no job with vj*≤ ∆ go to step(5). Step(3): Set t=t-pj*, N =N-{j*}, K=K-1, if K >1 go to step(1), otherwise go to step(4). Step(4): Compute Vmax(σ) for the sequence jobs σ =(σ(1) ,…, σ(n)) and ∆= Vmax -1, set t=Cmax, N={1,...,n}, K=n, σ= (φ), go to step(1). Step(5): Stop. Computational results for algorithm(3) for problem(P4): 8.1Test Problems: Algorithm(3) was tested by coding it in matlab 7.9.0(R2009b) and implemented on Intel Core (TM) i3 CPU M380 @ 2.53 GHZ, with RAM 4.00 GB personal computer. Test problems were generated as follows: for each job j, an integer processing time pj was generated from the uniform distribution [1,10]. Also, for each job j, an integer due date is generated from the distribution[pi,Σpi]. Results for 10,15, 30 and 50 job problems are given in Table (1) Because of page limitations, only five examples are given for each problem size. Table(1) should be read as follows: NEP = the actual number of efficient points for the problem at hand. Remember that the procedure finds all these points. MNEP = maximum possible number of efficient points for the problem at hand. Since an efficient point could exist for each value of the maximum late work between V(SPT*) and V(Lawler), this maximum possible number equals Vmax(SPT*) – Vmax(Lawler) + 1. From our computational results we conclude that: (a) The number of efficient points is usually small. Therefore, the decision maker should be able to make his choice. (b) We can find all efficient points. This allows for a justified choice of a sequence that takes both objective functions into account and that is not dominated by any other sequence. Very attractive efficient points are found for all the test problems. In most cases we discovered efficient point that were surprisingly close to the optimum value for both objectives. Remark 1: If we replace the criterion Vmax in problem(P4) by the criterion fmax {Lmax, Tmax, , } then the efficient Algorithm(3) above can be used for their solutions. Also for the 1//F(Σci, Tmax) problem, which is solved by Vanwassenhove and Gelder [11]. This means that algorithm(3) is a general one and simple that can solve problems of form 1//F(Σci, fmax). Analysis of the Three Criteria. Mathematics - 362 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 First, we present the main multicriteria scheduling results that have appeared in the literature. Hoogeveen[8] solves the problem 1//F(fmax, gmax) and the problem 1//F(fmax, gmax, hmax). He presented a polynomial algorithm for both problems and he showed that these can be used if precedence constraints exist between the jobs or if all penalty functions are non- decreasing in the job completion times. Hoogeveen[13] solves the general problem 1//F( ,…, ), k finite integer number and each one of these penalty functions is assumed to be non-decreasing in the job completion time. There are two methods for dealing with conflicting criteria, the first one is hierarchical minimization of the performance criteria , ,…, which are indexed in order of decreasing importance. The second method is simultaneous minimization. The criteria are aggregated into a single composite objective function F( , ,…, ), which minimized. In our study we are looking for algorithms, that can be used for solving multicriteria scheduling problem, which is to find the efficient solutions or at least approximation to it. Hence we search for feasible solutions yielding the best compromise among objectives that constitutes a so called efficient solutions set. The 1//F( , Tmax, Vmax) problem(P5): In this section, we will try to find efficient (Pareto optimal) solutions for 1//F(Σci ,Tmax, Vmax). This problem can be defined as: Min s.t. ci ≥ pi i=1,…,n. ci=c(i-1)+ pi i=2,…,n. ….. P(5) vi≤ pi i=1,…,n. vi≤ Ti i=1,…,n. Ti≥ ci - di i=1,…,n. Ti ≥ 0 i=1,…,n. It is clear that this problem is difficult to solve, we will present later local search algorithm to find near optimal solution. This problem has the following special cases. (1) The 1//Lex( , Tmax, Vmax) problem. (2) The 1//Lex( , Vmax, Tmax) problem. (3) The 1//Lex(Tmax, ,Vmax) problem. (4) The 1//Lex(Tmax, Vmax, ) problem. (5) The 1//Lex(Vmax, ,Tmax) problem. (6) The 1//Lex(Vmax, Tmax, ) problem. Algorithm(4) for finding efficient solutions for problem (P5): Mathematics - 363 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 Step(0): Put ∆= , N={1,…..,n}, K=n, t=Cmax= , and σ= (φ). Step(1): Calculate Ti , vi, i N as follows: Ti = Max {ci - di, 0}and vi=min{Ti, pi}. Step(2): Find a job j* N ,such that Tj*≤ ∆ and pj* > pi, j*, i N and Ti ≤ ∆, if pj*=pi choose the job with smallest Tj* and if Tj*=Ti choose the job with smallest vj*. Then assign job j* in position K of σ =(σ(K), σ ), If no job with Tj*≤ ∆ go to step(5). Step(3): Set t=t-pj*, N =N-{j*}, K=K-1, if K >1 go to step(1), otherwise go to step(4). Step(4): Compute Σcσ(i),Tmax(σ) and Vmax(σ) for the sequence jobs σ=(σ(1),…,σ(n)), and set ∆= Tmax(σ)-1, set t=Cmax, N={1,…..,n}, K=n, σ= (φ), go to step(1). Step(5): Put ∆=Vmax(σ)-1, N={1,...,n}, K=n, t=Cmax , and σ= (φ). Step(6): Calculate vi , i N as follows:       =≤+ =+<< =≤ = n 1,...,i ,ic ipid if ip n1,...,i ,ipid ic id if id- ic n1,...,i ,id ic if 0 iv Step(7): Find a job j* N, such that vj*≤ ∆ and pj* > pi , j*, i N and vi ≤ ∆, if pj*=pi choose the job with smallest vj*. Then assign job j* in position K of σ =(σ(K), σ ). If no job with vj*≤ ∆ go to step(10). Step(8): Set t=t-pj*, N=N-{j*}, K=K-1, if K >1 go to step(6), otherwise go to step(9) Step(9): Calculate Σcσ(i) , Tmax(σ) and Vmax(σ) for the sequence jobs σ=(σ(1),…,σ(n)), go to step(5). Step(10): Stop. The 1//F( Σwici, Tmax, Vmax) problem(P6): In this section, we will try to find efficient (Pareto optimal) solutions for 1//F(Σwici, Tmax, Vmax) problem. This problem can be defined as: Min s.t. ci ≥ pi i=1,…,n. ci = c(i-1)+ pi i=2,…,n. ….. P(6) vi ≤ pi i=1,…,n. vi ≤ Ti i=1,…,n. Ti ≥ ci - di i=1,…,n. Ti ≥ 0 i=1,…,n. Algorithm(5) for finding efficient solutions for problem(P6): Mathematics - 364 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 Step(0): Put ∆= , N={1,…..,n}, K=n, t=Cmax= , and σ= (φ). Step(1): Calculate Ti , vi, i N as follows: Ti = Max {ci - di , 0} and vi=min{Ti, pi}. Step(2): Find a job j* N, such that Tj*≤ ∆ and pj*/wj* > pi/wi, j*, i N and Ti ≤ ∆, if pj*/wj* = pi/wi choose the job with smallest Tj* and if Tj*=Ti choose the job with smallest vj*. Then assign job j* in position K of σ = (σ(K), σ ). If no job with Tj*≤ ∆ go to step(5). Step(3): Set t=t-pj*, N =N-{j*}, K=K-1, if K >1 go to step(1), otherwise go to step(4). Step(4): Compute Σwσ(i)cσ(i), Tmax(σ) and Vmax(σ) for the sequence jobs σ =(σ(1),…, σ(n)), and set ∆= Tmax(σ) -1, set t=Cmax= , N={1,…..,n}, K=n, σ= (φ) and go to step(1). Step(5): Put ∆=Vmax(σ)-1, N={1,...,n}, K=n, t=Cmax, and σ= (φ). Step(6): Calculate vi , i N as follows:           =≤+ =+<< =≤ = n 1,...,i ,c pd if p n1,...,i ,pd c d if d- c n1,...,i ,d c if 0 v iiii iiiiii ii i Step(7): Find a job j* N, such that vj*≤ ∆ and pj*/wj* > pi/wi , j*,i N and vi ≤ ∆, if pj*/wj* = pi/wi choose the job with smallest vj*. Then assign job j* in position K of σ =(σ(K), σ ). If no job with vj*≤ ∆ go to step(10). Step(8): Set t=t-pj*, N=N-{j*}, K=K-1, if K >1 go to step(6), otherwise go to step(9). Step(9): Calculate Σwσ(i)cσ(i), Tmax(σ) and Vmax(σ) for the sequence jobs σ =(σ(1),…,σ(n)), go to step(5). Step(10): Stop. Example(2):Consider the problem 1//F(Σwici,Tmax,Vmax) with the following data: i 1 2 3 4 5 pi 10 3 9 1 4 di 20 14 25 29 16 wi 4 1 8 5 2 pi/ wi 5/2 3 9/8 1/5 2 Hence, efficient sequences for the three-criterion problem(P6) of minimizing Σwici, Tmax and Vmax. SEQUENCES Σwici Tmax Vmax SWPT=(4,3,5,1,2) 236 13 4 (4,3,5,2,1) 238 7 7 (4,5,1,2,3) 309 4 3 (4,5,2,1,3) 311 2 2 (5,2,1,3,4) 426 1 1 Conclusions In this paper, the problems of scheduling jobs on one machine for a variety of multicriteria are considered. We proposed algorithms, which give all efficient solutions within the efficient range for the problems 1//F(Σfi, fmax), 1//F(Σfi, fmax , gmax), where Σfi= Σci and fmax, gmax {Lmax, Tmax, Vmax}. Mathematics - 365 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 References 1. Jackson J.R.(1955)."Scheduling a production line to minimize maximum tardiness" Res. Report 43 management science, Res. Project, University of California, Loss Angles, CA, 2. Smith W.E.(1956)."Various optimizers for single stage production", Naval Research Logistics Quarterly 3/1, 59-66. 3. Lawler E.L.(1973)."Optimal sequencing of a single machine subject to precedence constraints", Management Science 19/5, 544-546. 4. French S. (1982). "Sequencing and Scheduling : An introduction to the mathematical of the job shop ", John wiley and sons, New York. 5. Hoogeveen J.A. (2005)." Invited Review Multi-criteria scheduling ", European Journal of Operational Research 167, 592–623. 6. Fry TD, Armstrong RD. Lewis, H. (1989). "A framework for single machines Multiple objective sequencing research", OMEGA; 17 (6): 595-607. 7. Landa silva E. K. and Burke S. Petrovic ,"An Introduction to Multiobjective Metaheuristics for Scheduling and Time tabling " 8. Hoogeveen, J.A. (1996).” Single machine scheduling to minimize a function of two or three maximum cost criteria “ , Journal of Algorithms, 21,415-433. 9. Bagchi T.P., (1999). "Multiobjective Scheduling by Genetic Algorithms", Kluwer Acadimic publisher. 10. Hoogeveen, J.A. and van de Velde, S.L. (1995). “ Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time”, Operations Research Letters 17, 205–208. 11. Van Wassenhove, L.N. and Gelders. F. (1980). "Solving a bicriterion scheduling problem", European Journal of Operational Research 4/1, 42-48. 12. Emmons, H. (1975). "A note on a scheduling problem with dual criteria", Naval Res. Logis. Quarterly, 22, 615-516 . 13. Hoogeveen, J.A. (1991). ” Single machine scheduling to minimize a function of K maximum cost criteria “ ,CWI,BS-R9113. Table(1): Computational results Problem Size Problem Number NEP MNEP Efficient Points 10 1 2 2 (273, 8), (262, 9) 2 2 2 (208, 8), (189, 10) 3 4 4 (290, 7), (227, 8), (211, 9), (202, 10) 4 1 1 (194, 10) 5 3 4 (353, 7), (317, 8), (293, 10) 15 1 3 3 (388, 8), (354, 9), (337, 10) 2 2 2 (657, 9), (571, 10) 3 3 4 (752, 7), (613, 9), (511, 10) 4 2 2 (599, 9), (501, 10) 5 2 2 (618, 8), (474, 9) 30 1 4 4 (2737, 7), (2418, 8), (2283, 9), (2206, 10) 2 2 2 (1833, 9), (1755, 10) 3 4 4 (2275, 7), (2165, 8), (1861, 9), (1749, 10) 4 6 6 (2599, 5), (2499, 6), (2384, 7), (2283, 8), (2226, 9), (2214, 10) 5 1 1 (1982,10) 50 1 5 5 (6192, 6), (5869, 7), (5477, 8), (5110, 9), (4863, 10) 2 2 2 (6223, 9), (5518) 3 4 4 (5945, 7), (5794, 8), (5437, 9), (5228, 10) 4 6 6 (5715, 4), (5276, 5), (5105, 6), (4810, 7), (4652, 8), (4641, 9) 5 2 2 (5432, 10), (6607, 9) Mathematics - 366 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 3 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 3 Vol. 25 Year 2012 مجموع أوقات اإلتمام مع أعظم عمل تأخير فراس شاكر فندي و صالح عبد الرزاقطارق قسم الرياضيات، كلية العلوم، الجامعة المستنصرية. للعلوم الصرفة، جامعة األنبار قسم الرياضيات، كلية التربية 2012نيسان 22قبل البحث: 2012نيسان 1استلم البحث في: الخالصة هذا البحث المسألة لجدولة الوظائف على الماكنة الواحدة للمعايير المتنوعة درست المسألة لتصغير مجموع في من الوظائف المستقلة التي يمكن جدولتها على ماكنة واحدة والتي nمع أعظم عمل تأخير. المجموعة أوقات اإلتمام وصاعدا ولذلك ال يمكن ان تعالج اكثر من وظيفة واحد في وقت واحد. الوظيفة 0تتطلب معالجة باستمرار من الوقت صفر i تتطلب وقت معالجة موجب معطى مستمر pi الموعد المثالي إلكمال الوظيفة ،di . معايرها فوءة في حالة المسائل التيلمسائل جدولة المعايير الثنائية ، بعض الخوارزميات اقترحت إليجاد الحلول الك ، فقد اقترحنا خوارزميات عامة إلعطاء الحلول الكفوءة ضمن المدى ايضالمسائل المعايير المتعددة و. متساوية األهمية الكفوء. الجدولة، المعايير المتعددة، الماكنة الواحدة، المعايير الثنائية. -الكلمات المفتاحية: