Preemptive Semi–online Algorithms for Parallel Machine Scheduling with Known Total Size

Yong He; Hao Zhou; Yi Wei Jiang
April 2006
Acta Mathematica Sinica;Apr2006, Vol. 22 Issue 2, p587
Academic Journal
This paper investigates preemptive semi-online scheduling problems on m identical parallel machines, where the total size of all jobs is known in advance. The goal is to minimize the maximum machine completion time or maximize the minimum machine completion time. For the first objective, we present an optimal semi–online algorithm with competitive ratio 1. For the second objective, we show that the competitive ratio of any semi–online algorithm is at least $$ \frac{{2m - 3}} {{m - 1}} $$ for any m > 2 and present optimal semi–online algorithms for m = 2, 3.


Related Articles

  • Extra Processors versus Future Information in Optimal Deadline Scheduling. Chiu-Yuen Koo; Tak-Wah Lam; Tsuen-Wan "Johnny" Ngan; Kar-Keung To // Theory of Computing Systems;May/Jun2004, Vol. 37 Issue 3, p323 

    This paper is concerned with the design of online scheduling algorithms that exploit extra resources. In particular, it studies how to make use of multiple processors to counteract the lack of future information in online deadline scheduling. Our results extend the previous work that are...

  • From External to Internal Regret. Blum, Avrim; Mansour, Yishay // Journal of Machine Learning Research;6/1/2007, Vol. 8 Issue 6, p1307 

    External regret compares the performance of an online algorithm, selecting among N actions, to the performance of the best of those actions in hindsight. Internal regret compares the loss of an online algorithm to the loss of a modified online algorithm, which consistently replaces one action by...

  • ON THE POWER OF RANDOMIZATION FOR JOB SHOP SCHEDULING WITH κ-UNITS LENGTH TASKS. Mömke, Tobias // RAIRO -- Theoretical Informatics & Applications;2009, Vol. 43 Issue 2, p189 

    In the job shop scheduling problem k-units-Jm, there are m machines and each machine has an integer processing time of at most k time units. Each job consists of a permutation of m tasks corresponding to all machines and thus all jobs have an identical dilation D. The contribution of this paper...

  • Online Job Dispatching and Scheduling to Minimize Job Completion Time and to Meet Deadlines. LI, YUPENG // Journal of Interconnection Networks;Dec2018, Vol. 18 Issue 4, pN.PAG 

    In this paper, we study the problem of job dispatching and scheduling, where each job consists of a set of tasks. Each task is processed by a set of machines simultaneously. We consider two important performance metrics, the average job completion time (JCT), and the number of deadline-aware...

  • The Lazy Adversary Conjecture Fails. Peserico, Enoch // Theory of Computing Systems;May/Jun2004, Vol. 37 Issue 3, p397 

    In the context of competitive analysis of online algorithms for the k-server problem, it has been conjectured that every randomized, memoryless online algorithm exhibits the highest competitive ratio against an offline adversary that is lazy, i.e., that will issue requests forcing it to move one...

  • Online algorithms: a survey. Albers, Susanne // Mathematical Programming;Jul2003, Vol. 97 Issue 1/2, p3 

    During the last 15 years online algorithms have received considerable research interest. In this survey we give an introduction to the competitive analysis of online algorithms and present important results. We study interesting application areas and identify open problems.

  • Autonomic query parallelization using non-dedicated computers: an evaluation of adaptivity options. Norman Paton; Jorge Buenabad-Chavez; Mengsong Chen; Vijayshankar Raman; Garret Swart; Inderpal Narang; Daniel Yellin; Alvaro Fernandes // VLDB Journal International Journal on Very Large Data Bases;Jan2009, Vol. 18 Issue 1, p119 

    Abstract  Writing parallel programs that can take advantage of non-dedicated processors is much more difficult than writing such programs for networks of dedicated processors. In a non-dedicated environment such programs must use autonomic techniques to respond to the unpredictable load...

  • A query algorithm for online analytical processing queries evaluation based on mediate index bucket. Ai-qin Liu; Ji-fu Zhang; Ya-ling Xun // Journal of Communication & Computer;Apr2007, Vol. 4 Issue 4, p14 

    How to improve the performance of joining and aggregation is a key problem for OLAP query processing. This paper proposes a query algorithm MIBGA (Grouping and Aggregation based on Mediate Index Bucket). The algorithm efficiently integrates fact table grouping sets into dimension hierarchical...

  • Parametric Primitives for Hand Gesture Recognition. Krüger, Volker // World Academy of Science, Engineering & Technology;Oct2009, Issue 34, p97 

    Imitation learning is considered to be an effective way of teaching humanoid robots and action recognition is the key step to imitation learning. In this paper an online algorithm to recognize parametric actions with object context is presented. Objects are key instruments in understanding an...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics