Computing 72, 355–363 (2004) Digital Object Identifier (DOI) 10.1007/s00607-003-0034-2

Semi-Online Algorithms for Parallel Machine Scheduling Problems* G. Do´sa, Veszpre´m, and Y. He, Hangzhou

Received May 19, 2003; revised October 8, 2003 Published online: January 20, 2004 Ó Springer-Verlag 2004 Abstract This paper considers two semi-online versions of scheduling problem P 2jjCmax where one type of partial information is available and one type of additional algorithmic extension is allowed simultaneously. For the semi-online version where a buffer of length 1 is available and the total size of all jobs is known in advance, we present an optimal algorithm with competitive ratio 5=4. We also show that it does not help that the buffer length is greater than 1. For the semi-online version where two parallel processors are available and the total size of all jobs is known in advance, we present an optimal algorithm with competitive ratio 6=5. AMS Subject Classifications: 90B35, 90C27. Keywords: scheduling, semi-online, approximation algorithm, competitive analysis.

1. Introduction In most classical literature of scheduling theory, problems are classified as off-line and on-line [3]. If full information on jobs to be scheduled is available in advance, we call the scheduling problem off-line. By contrast, if the jobs are not known a prior, but arrive one by one, and we are required to schedule jobs irrevocably on the machines as soon as they are given, without any knowledge about jobs that follow later on, this problem is called on-line. In recent years, semi-online scheduling problems have received increasing attention from the scheduling community due to their much application in practice [2, 9, 10]. Here a scheduling problem is called semi-online if some partial additional information about jobs is available in advance, or additional algorithmic extension is possible. Semi-online is neither off-line nor on-line, but somehow in between. Though it is a relatively new area, various papers and enormous results were appeared in the last decade [2, 4, 7–11, 13–17].


The second author is supported by TRAPOYT of China, National Natural Science Foundation of China (10271110). Corresponding author: Y. He.

356

G. Do´sa and Y. He

Algorithms for on-line (semi-online) problems are called on-line (semi-online) algorithms. We use competitive analysis to measure their performance. Competitive analysis is a type of worst-case analysis where the performance of an on-line or semi-online algorithm is compared to that of an optimal off-line algorithm [12]. For an on-line or semi-online algorithm A, let CA denote the makespan produced by A and COPT denote the optimal makespan in an off-line version. Then the competitive ratio of A is defined as the smallest number q such that CA  qCOPT for all instances. An online or semi-online problem has a lower bound q if no online or semi-online algorithm can have a smaller competitive ratio. An on-line or semi-online algorithm is called optimal if its competitive ratio matches the lower bound of the on-line or semi-online problem. In general, in a semi-online version of a problem the conditions to be considered on-line are somehow relaxed. Different ways of relaxing the conditions give rise to different semi-online versions, one wishes to achieve improvement of the performance of the optimal semi-online algorithm with respect to the on-line version [9]. Let us consider the most classical scheduling problem P 2jjCmax [6, 1] in the following. For this scheduling problem, we are confronted with a sequence of independent jobs with positive processing times (sizes) p1 ; p2 ; . . . ; pn , that must be scheduled on two parallel identical machines M1 ; M2 . We identify the jobs with their processing times. The machines are available at time zero and no preemption is allowed. The load of a machine is the sum of the processing times of jobs assigned to that machine. The objective is to minimize the maximum machine load Cmax , called makespan. It is well-known [5, 6] that List Scheduling ðLSÞ is an optimal on-line algorithm with competitive ratio 3=2. The ratio can be tightened to ð1 þ rÞ=2 if jobs are tightly-grouped [8], i.e., all job sizes are in the interval ½p; rp for some p > 0 and 1  r  2. Several types of partial information are proposed to get algorithms with smaller competitive ratios. For example, the total size of all jobs is known in advance [9], the largest size of jobs is known in advance [8], the optimal makespan is known as a prior [2], all jobs come in the non-increasing order of their sizes [11], etc. On the other hand, Kellerer, Kotov, Speranza and Tuza [9] considered the versions where one type of additional algorithm extension is allowed. For example, a buffer is available where some of jobs can be stored, two parallel processors are available which allows to yield two schedules simultaneously and best one is chosen at last, etc. The first version was also studied by Zhang [16]. It has been shown that for the version with non-increasing job sizes, optimal semi-online algorithm has competitive ratio 7=6, and for all above remaining versions, optimal semi-online algorithms have competitive ratio 4=3. To further shed light on usefulness of different types of information, some papers considered whether the combination of two types of information can admit to construct a semi-online algorithm with much smaller competitive ratio than that of the case where only one type of information is available in advance. Tan and He [15] presented several kinds of combination which make no sense. Moreover they showed in the same paper that if both the total size and largest size of all jobs are known in advance, or if the total size is known in advance and all jobs come in non-increasing order of their sizes, optimal algorithms have competitive ratios

Semi-Online Algorithms for Parallel Machine Scheduling Problems

357

6=5; 10=9, respectively. Zhang and Ye [17] considered the combination of information suggestive and Largest Last. The first type of information means that at the time the last job arrives, the scheduler is informed that it is indeed the last one. The second one means that the last job p isffiffiffithe largest one. They proposed an optimal algorithm with competitive ratio 2 while each type of above information itself is useless [15]. Epstein [4] showed that if the optimal value is known in advance and the jobs come in non-increasing order of sizes, optimal algorithm has competitive ratio 10=9. In this paper, we continue this investigation in different way. We study the semionline versions where one type of partial information and one type of additional algorithmic extension are combined. Two versions are considered. For the semionline version where a buffer of length 1 is available and the total size of all jobs is known in advance, we present an optimal algorithm with competitive ratio 5=4 in Sect. 2. We also show that it does not help that the buffer length is greater than 1 in the same section. For the semi-online version where two parallel processors are available and the total size of all jobs is known in advance, we present an optimal algorithm with competitive ratio 6=5 in Sect. 3.

2. Semi-Online Version with a Buffer and Known Total Size In this section, we assume that jobs arrive one by one and the total size of all jobs is known in advance. Furthermore, we assume that a buffer of length l  1 is available to maintain l job. Therefore, in the case that the buffer is not completely occupied, an incoming job can either be immediately assigned to a machine or be temporarily put into the buffer. If l jobs are stocked in the buffer, the incoming job can either be assigned to a machine, or be put in the buffer while one job in the buffer must be immediately assigned to a machine. For l ¼ 1, we present an algorithm ALG1 with competitive ratio 5=4. We further show that for any l  1, any algorithm has competitive ratio at least 5=4. Therefore algorithm ALG1 is optimal, and it does not help that the buffer length is greater than 1. Denote by T the total size of all jobs. By normalizing the sizes of all jobs, we assume T ¼ 8. Denote by s1 and s2 the current loads of machines M1 and M2 , respectively. The main idea of the algorithm is as follows. The first job is put into the buffer. Denote by X the job which is put into the buffer. For the newlyincoming job pk , maxfpk ; X g is chosen to be put into the buffer, and minfpk ; X g (denoted by Y ) is assigned immediately. Thus X is the largest one of the first k jobs. Through the algorithm we try to hold the conditions s2  1 and s2  s1  s2 þ 2. If these conditions has to be violated, the incoming jobs will be assigned in an appropriate way. Algorithm ALG1 1. Let s1 ¼ s2 ¼ 0; X ¼ p1 ; k ¼ 1. 2. k ¼ k þ 1. If no new job comes, then assign X to M2 and stop.

358

G. Do´sa and Y. He

Let Y ¼ minfpk ; X g; X ¼ maxfpk ; X g. If s1 þ Y  s2 þ 2, then assign Y to M1 , let s1 ¼ s1 þ Y , go to 2. If s2 þ Y  1, then assign Y to M2 , let s2 ¼ s2 þ Y , go to 2. If there is a job Z 2 fX ; Y g and i 2 f1; 2g such that si þ Z 2 ½3; 5, then assign Z to Mi , the another one in fX ; Y g and all remaining jobs to another machine, and end. If there is an index i 2 f1; 2g such that si þ X þ Y 2 ½3; 5, then assign X and Y to Mi , all remaining jobs to another machine, and end. 7. If s1 þ X > 5, then assign X to M2 , assign all remaining jobs to M1 and end. 8. If s1 þ X < 3, then assign X to M1 , assign Y to M2 . And assign all remaining jobs according to the following rule: If the size of newlyincoming job is greater than 2, assign it to M2 . In the opposite case assign it to M1 . If the current load of M1 is in the interval ½3; 5, then assign all subsequent jobs to M2 and end.

3. 4. 5. 6.

Theorem 2.1. The competitive ratio of ALG1 is at most 5=4. Proof. It is clear that algorithm ALG1 must stop at one of Steps 2 and 6-8. If it stops at Step 2, then X is the last unassigned job, s2  1 and s1  s2 þ 2 hold when the algorithm enters Step 2. Thus s1 þ s2 < 4 and X ¼ 8  ðs1 þ s2 Þ > 4. It follows that the optimal value is COPT  X > 4 and CALG1 ¼ maxfs1 ; s2 þ X g ¼ s2 þ X . Therefore CALG1 ¼ X þ s2  X þ 1 < X þ X4  54 COPT . When the algorithm enters one of Steps 6-8, the current loads of two machines satisfy s2  s1  s2 þ 2; s2  1; s1 þ Y > s2 þ 2 and s2 þ Y > 1. If the algorithm stops at Step 6, it is clear that CALG1 =COPT  5=4 . Now assume that the algorithm does not stop at Step 6. We show that in this case s1 þ Y < 3 holds. In fact, to avoid that the algorithm enters Step 6, either s1 þ Y < 3 or s1 þ Y > 5 holds. If s1 þ Y > 5, then s2 þ 2 þ X  s1 þ X > 5, and this yields s1 þ s2 þ X þ Y > 8, a contradiction. Thus we get s1 þ Y < 3. If the algorithm stops at Step 7. Then s1 þ Y < 3 and s1 þ X > 5 . Thus X > Y þ 2. Furthermore from s2 þ Y > 1, we get s2 þ X > 3. It follows that s2 þ X > 5, otherwise the algorithm ends at Step 6. Hence s2  1 implies X > 4, which deduces that COPT  X > 4. We get again that CALG1 ¼ X þ s2  X þ 1 < 54 X  54 COPT . Lastly we consider the case that the algorithm stops at Step 8. Then s1 þ X < 3. It follows that Y  X < 3. Note that s1 þ X  s1 þ Y > s2 þ 2 and s2 þ Y > 1, we get s1 þ X þ Y > s2 þ 2 þ Y > 3. The algorithm does not stop at Step 6, thus s1 þ X þ Y > 5. s1  s2 þ 2 implies s2 þ X þ Y > 3, and thus s2 þ X þ Y > 5. It follows from s2  1 that X þ Y > 4, and thus X > 2. Because s1 þ X < 3 we get s1 < 1. It is easy to see that in this case s2 ¼ 0 must hold by the algorithm rule, and thus X þ Y > 5.

Semi-Online Algorithms for Parallel Machine Scheduling Problems

359

If all new incoming jobs have sizes no greater than 2, there must be a job such that assigning it to M1 forces its new load to be in the interval ½3; 5, then CALG1 =COPT  5=4. Hence we suppose that there is a job, denoted by J , with size J > 2. Then J  8  X  Y < 3. Note that immediately before J comes, only Y has been assigned to M2 , thus only Y and J are finally assigned to M2 . If Y þ J  5, the result is trivially true due to Y þ J > 4. Suppose that Y þ J > 5. If J  X , then everyone of jobs X ; Y and J has size larger than 2 and maxfX ; Y ; J g ¼ X . It means that in the optimal schedule Y and J must be assigned to one machine, and all other jobs to another machine. Hence algorithm ALG1 yields an optimal schedule. In the opposite case, we know J > X and J is the largest job. Hence the optimal makespan is COPT ¼ Y þ X > 5, and CALG1 ¼ Y þ J < 6 < 54 COPT . The proof is complete. ( Theorem 2.2. The competitive ratio of any algorithm is at least 5=4 even the buffer length is greater than 1. Proof. Assume the buffer length l  1. We show the result by presenting sequences for which the optimal makespan is 4n þ 1 and any algorithm A yields a solution with makespan at least 5n þ 2  l. Hence CA =COPT  ð5n þ 2  lÞ=ð4n þ 1Þ ! 5=4 ðn ! 1Þ. Let the total size of all jobs be 8n þ 2 ¼ 2ð4n þ 1Þ, where n ¼ 2k and k is integer with k  4. In the following, denote by ðs1 ; s2 Þ the current loads of machines ðM1 ; M2 Þ yielded by algorithm A at the time when all arriving jobs except l jobs in buffer have been assigned to machines. Firstly, the first 3n jobs with unit size arrive. Before the arrival of the 3n þ 1-th job, l jobs with unit size is in buffer. Hence we have s1 þ s2 ¼ 3n  l. W. l. o. g., we assume s1  s2 . Before the arrival of 3n þ 1-th job, if we have ðs1 ; s2 Þ ¼ ð3n  l; 0Þ, then the next and last two jobs with size 2:5n þ 1 arrive. If they are assigned to the same machine, then the final load of this machine is at least 5n þ 1. If they are assigned to different machines, the final load of M1 is 3n  l þ 2:5n þ 1 ¼ 5:5n  l þ 1  5n  l þ 2 due to n  2. Hence we conclude that s2  1 before the arrival of 3n þ 1-th job. Now 3n þ 1-th and 3n þ 2-th jobs with unit size arrive. Before the arrival of 3n þ 3-th job, if we have ðs1 ; s2 Þ ¼ ð3n þ 1  l; 1Þ or ðs1 ; s2 Þ ¼ ð3n  l; 2Þ, then the next and last two jobs with size 2:5n arrive. If these jobs are assigned to the same machine, then the final load of this machine is at least 5n þ 1. Otherwise the final load of M1 is at least 3n  l þ 2:5n ¼ 5:5n  l  5n þ 2  l since n  4. Thus it can be assumed that s2  3 before the arrival of 3n þ 3-th job. Generally, we show the following property is true by induction: If we have s2  2j þ 1 before the arrival of 3n þ 2j þ 1-th job, then s2  2j þ 3 is valid right after 3n þ 2j þ 1-th and 3n þ 2j þ 2-th jobs with unit size arrive, where j ¼ 0; 1;    ; k  2.

360

G. Do´sa and Y. He

It is clear that the property holds for j ¼ 0 as shown above. Assume that it holds for some j  1, j  k  2, that is, we have s2  2j þ 1 before the arrival of 3n þ 2j þ 1-th job. Now 3n þ 2j þ 1-th and 3n þ 2j þ 2 jobs with unit size arrive. Then the new loads of two machines satisfy s1 þ s2 ¼ 3n þ 2j þ 2  l. If s2  2j þ 2, then the next and last two jobs with size 2:5n  j arrive. If these two jobs are assigned to the same machine, the final load of this machine is at least 2ð2:5n  jÞ þ 2j þ 1 ¼ 5n þ 1 since s2  2j þ 1 by induction assumption. Otherwise the final load of M1 is at least 3n  l þ 2:5n  j ¼ 5:5n  j  l  5n þ 2  l since n  2j þ 4. Thus we get s2  2j þ 3 right after 3n þ 2j þ 1-th and 3n þ 2j þ 2 jobs with unit size arrive, i.e., the property holds for j, i.e. it holds for all j ¼ 0; 1;    ; k  2. Finally we assume that there are totally 3n þ 2ðk  2Þ þ 2 ¼ 3n þ n  2 arrived jobs, all with unit size. By the above property, we conclude that algorithm A yields a schedule with s2  2ðk  2Þ þ 3 ¼ 2k  1 ¼ n  1. Now again two jobs with unit size arrive. If at least one job is assigned to M2 such than s2 > n  1, then the last two jobs arrive, one with size 4n þ 1 and another with size 1. Therefore there is one machine such that its load is at least 5n þ 1. Otherwise we have ðs1 ; s2 Þ ¼ ð3n  l þ 1; n  1Þ. In this case the last two jobs with size 2n þ 1 arrive, and the statement is thus proved. ( Remark 1. Consider the following related semi-online version: We know the total size of all jobs in advance, furthermore we are allowed to lookahead, i.e., we always know the sizes of next l  1 incoming jobs. For this problem, we can easily show that no algorithm can guarantee a smaller competitive ratio than 4=3 by considering the following sequences: p1 ¼ p2 ¼ T =6; p3 ¼    ¼ plþ2 ¼
; plþ3 ¼ plþ4 ¼ 2T =6  l
=2, and p1 ¼ p2 ¼ T =6; p3 ¼    ¼ plþ2 ¼
; plþ3 ¼ T =2; plþ4 ¼ T =6  l
, where T is the total size of all jobs, and
is a sufficiently small positive number. Therefore we conclude lookahead is useless when the total size of all jobs is known in advance. 3. Semi-Online Version with Two Parallel Processors and Known Total Size In this section, we assume that jobs arrive one by one and the total size of all jobs is known in advance. Furthermore, two parallel processors, each consisting of two identical machines, are available for the computation of the solution. One copy is made of each incoming job, and each of two identical copies has to be assigned to a machine by each of two processors before the arrival of the subsequent jobs. Finally, the best of two solutions independently yielded by two processors is chosen. We present an optimal algorithm ALG2 for this semi-online problem with competitive ratio 6=5. For the discussed problem, we call two solutions independently yielded by two processors as schedules a and b. In the remainder of this section, we assume the total size of all jobs is T ¼ 10 by normalizing the sizes of all jobs. Denote by s1 and s2 the current loads of machines M1 ; M2 in schedule a, respectively. Denote by t1 and t2 the current loads of machines M1 ; M2 in schedule b,

Semi-Online Algorithms for Parallel Machine Scheduling Problems

respectively. Define k ¼ minfjj

j P

361

pi  4g and denote pk ¼ Y . Note that there is at

i¼1

most one job which arrives before pk and has size greater than 2. If there is such a job, denote it by X . Denote by Z the first job which arrives after pk and has size greater than 2, if it exists. In algorithm ALG2, schedules a and b are constructed independently as follows: Schedule a of algorithm ALG2 1. Let s1 ¼ s2 ¼ 0; l ¼ 1. 2. If s1 þ pl < 4, then assign pl to M1 , let s1 ¼ s1 þ pl , and go to 5. 3. If 4  s1 þ pl  6, then assign pl to M1 , assign all remaining jobs to M2 , and end. 4. If s1 þ pl > 6, then assign pl to M2 , let s2 ¼ s2 þ pl , and go to 5. 5. l ¼ l þ 1. If no new job comes, then end. Otherwise go to 2. Schedule b of algorithm ALG2 1. Let t1 ¼ l t2 ¼ 0; l ¼ 1. P pi  2, assign pl to M1 , let t1 ¼ t1 þ pl and l ¼ l þ 1. 2. While l i¼1 P 3. While 2 < pi < 4, assign pl by algorithm LS, and modify appropriately t1 i¼1

and t2 , let l ¼ l þ 1. 4. If 4  Y þ ti  6 for some i 2 f1; 2g, then assign Y to Mi , assign all remaining jobs to the other machine, and end. 5. Assign Y to M1 . 6. Assign all remaining jobs to M1 except Z, if there exists job Z, then assign it to M2 . Remark 2. Consider schedule b right after Step 3. There can be two possibilities: (i). If job X does not exist, then at this moment jt1  t2 j  2. (ii). In the opposite case, only X is assigned to M2 currently. We say that a schedule is appropriate, if it has a makespan no greater than 6 after assigning all jobs. It is obvious that CALG2 =COPT  6=5 if schedule a or b yielded by ALG2 is appropriate. Theorem 3.1. The competitive ratio of ALG2 is at most 6=5. Proof. Consider the moment when Y just comes. We can assume that s1 þ Y > 6, otherwise schedule a is appropriate. First assume that there does not exist job X . At this time all arrived jobs are assigned to M1 in schedule a, thus the following results hold: s2 ¼ 0, t1 þ t2 ¼ s1 < 4. By s1 þ Y  6, we have Y > 2. By Remark 2, we have jt1  t2 j  2. We consider the following three cases:

362

G. Do´sa and Y. He

Case 1. ti þ Y < 4; i ¼ 1; 2. In this case t1 þ t2 þ 2Y ¼ s1 þ 2Y < 8. From s1 þ Y > 6, we get Y < 2, a contradiction. Case 2. ti þ Y  4; i ¼ 1; 2. Then we have ti þ Y > 6 otherwise b is appropriate. It follows that t1 þ t2 þ 2Y ¼ s1 þ 2Y > 12. From s1 < 4, we get Y > 4. Then in schedule a only Y is assigned to M2 at this moment. If Y  6 then schedule a is appropriate. If Y > 6 then schedule a is optimal solution. Case 3. There exist i; j 2 f1; 2g; i 6¼ j; such that ti þ Y < 4 and tj þ Y  4. Thus tj þ Y > 6 and jt1  t2 j > 2, a contradiction again. Now assume that there exists job X . When job Y comes, only X is assigned to M2 in schedule b. If X þ Y  6, then schedule b stops at Step 4 and is appropriate. Hence we assume that X þ Y > 6. Immediately after assigning Y , in schedule a only Y , and in schedule b only X is assigned to M2 . If Y  4, then by the same argument as in Case 2 we know that schedule a is appropriate or optimal. Thus we have Y < 4. If there does not exist job Z, i.e. the sizes of all subsequent jobs are less than 2, then schedule a stops at Step 3, and is appropriate. Hence we assume that there exists job Z. Recall that when Y arrives, s1 þ Y > 6 holds, thus the total size of the remaining jobs is less than 4. Hence there is only one job which arrives after Y and has size greater than 2. If job Z is assigned to M1 in schedule a then this schedule is appropriate. Otherwise job Z is assigned to M2 in both schedules a and b. Finally in schedule a only Y and Z, and in schedule b only X and Z are assigned to M2 . If X þ Z  6 or Y þ Z  6, then one of the schedules is appropriate. Thus assume that X þ Z > 6 and Y þ Z > 6. If Z < maxf X ; Y g, then one of the schedules is optimal. In the opposite case Z is the largest job, and the optimal makespan is COPT ¼ Y þ X > 6. If further X þ Z  65 ðY þ X Þ or Y þ Z  65 ðY þ X Þ, then CALG2 =COPT  6=5. Hence Y þ Z > 65 ðY þ X Þ and X þ Z > 65 ðY þ X Þ. Then by simple calculation, we get Z > 4 and thus X þ Y þ Z > 10 ¼ T , a contradiction, and the theorem is proved. ( Theorem 3.2. The competitive ratio of any algorithm A is at least 6=5. Proof. Let the sum of the sizes of all job be 10. The first four jobs with unit size come. If after assigning these jobs in two schedules, we have minfs1 ; s2 ; t1 ; t2 g  1, i.e. in both schedules there are at least one job assigned to each machine, then last two jobs come, one with size 5 and another with size 1. It is clear that CA =COPT  6=5. In the opposite case, the current machine loads of one schedule is ð4; 0Þ. W. l. o. g., we assume that ðs1 ; s2 Þ ¼ ð4; 0Þ at this moment. If ðt1 ; t2 Þ 2 fð4; 0Þ; ð3; 1Þg, then the last two jobs with size 3 come. If ðt1 ; t2 Þ ¼ ð2; 2Þ; then the last two jobs have sizes 4 and 2, respectively. In all cases, we always have CA =COPT  6=5. (

Semi-Online Algorithms for Parallel Machine Scheduling Problems

363

Acknowledgement The authors wish to thank an anonymous referee and editor for their valuable comments.

References [1] Albers, S.: Better bounds for on-line scheduling. SIAM Journal on Computing 29, 459–473 (1999). [2] Azar, Y., Regev, O.: Online bin stretching. Theoretical Computer Science 268, 17–41 (2001). [3] Chen, B., Potts, C. N., Woeginger, G.: A review of machine scheduling: Complexity, algorithms and approximability. In: Du, D.-Z., Pardalos, P. M. (eds.), Handbook of combinatorial optimization. Kluwer Academic Publishers 1998. [4] Epstein, L.: Bin stretching revisted. Acta Informatica 39, 987–117 (2003). [5] Faigle, U., Kern, W., Tura´n, G.: On the performance of on-line algorithm for particular problems. Acta Cybernetica 9, 107–119 (1989). [6] Graham, R. L.: Bounds for certain multiprocessing anomalies. The Bell System Technical Journal 45, 1563–1581 (1996). [7] He, Y., Tan, Z. Y.: Ordinal online scheduling for maximizing the minimum machine completion time. Journal of Combinatorial Optimization 6, 199–206 (2002). [8] He, Y., Zhang, G. C.: Semi on-line scheduling on two identical machines. Computing 62, 179–187 (1999). [9] Kellerer, H., Kotov, V., Speranza, M. G., Tuza, Z.: Semi on-line algorithms for the partition problem. Operations Research Letters 21, 235–242 (1997). [10] Liu, W. P., Sidney, J. B., van Vliet, A.: Ordinal algorithms for parallel machine scheduling. Operations Research Letters 18, 223–232 (1996). [11] Seiden, S., Sgall, J., Woeginger, G.: Semi-online scheduling with decreasing job sizes. Operations Research Letters 27, 215–227 (2000). [12] Sleator, D., Tarjan, R. E.: Amortized efficiency of list update and paging rules. Communications of the ACM 28, 202–208 (1985). [13] Tan, Z. Y., He, Y.: Semi-on-line scheduling with ordinal data on two uniform machines. Operations Research Letters 28, 221–231 (2001). [14] Tan, Z. Y., He, Y.: Ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times. Computers & Mathematics with Applications 43, 1521–1528 (2002). [15] Tan, Z. Y., He, Y.: Semi-on-line problems on two identical machines with combined partial information. Operations Research Letters 30, 408–414 (2002). [16] Zhang, G. C.: A simple semi-online algorithm for P 2jjCmax with a buffer. Information Processing Letters 61, 145–148 (1997). [17] Zhang, G. C., Ye, D. S.: A note on on-line scheduling with partial information. Computers & Mathematics with Applications 44, 539–543 (2002). G. Do´sa Department of Mathematics University of Veszpre´m Veszpre´m Hungary e-mail: [email protected]

Y. He Department of Mathematics Zhejiang University Hangzhou 310027 P. R. China and State Key Lab of CAD & CG Zhejiang University Hangzhou 310027, P.R. China e-mail: [email protected]