TITLE

Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors

AUTHOR(S)
Bianco, L.; Blazewicz, J.; Dell'Olmo, P.; Drozdowski, M.
PUB. DATE
June 1995
SOURCE
Annals of Operations Research;1995, Vol. 58 Issue 1-4, p493
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
In the classical scheduling theory, it is widely assumed that a task can be processed by only one processor at a time. With the rapid development of technology, this assumption is no longer valid. In this work we present a problem of scheduling tasks, each of which requires for its processing a set of processors simultaneously and which can be executed on several alternative sets of processors. Scheduling algorithms based on dynamic and linear programming are presented that construct minimum length non-preemptive and preemptive schedules, respectively. Results of computational experiments are also reported.
ACCESSION #
18651774

 

Related Articles

  • A DYNAMIC PROGRAMMING ALGORITHM FOR PREEMPTIVE SCHEDULING OF A SINGLE MACHINE TO MINIMIZE THE NUMBER OF LATE JOBS. Lawler, E. L. // Annals of Operations Research;1990, Vol. 26 Issue 1-4, p125 

    The scheduling problem 1 ∣pmtn, rj ∣Σ wj Uj calls for n jobs with arbitrary release dates and due dates to be preemptively scheduled for processing by a single machine, with the objective of minimizing the sum of the weights of the late jobs. A dynamic programming algorithm for this...

  • SCHEDULING UNIT - TIME TASKS ON FLOW - SHOPS UNDER RESOURCE CONSTRAINTS. Błażewicz, J.; Kubiak, W.; Szwarcfiter, J. // Annals of Operations Research;1988, Vol. 16 Issue 1-4, p255 

    We consider the problem of scheduling tasks on flow shops when each task may also require the use of additional resources. It is assumed that all operations have unit lengths, the resource requirements are of 0–1 type and there is one type of the additional resource in the system. It is...

  • EARLINESS-TARDINESS SCHEDULING PROBLEMS, II: DEVIATION OF COMPLETION TIMES ABOUT A RESTRICTIVE COMMON DUE DATE. Hall, Nicholas G.; Kubiak, Wieslaw; Sethi, Suresh P. // Operations Research;Sep/Oct91, Vol. 39 Issue 5, p847 

    A companion paper (Part I) considers the problem of minimizing the weighted earliness and tardiness of jobs scheduled on a single machine around a common due date, d, which is unrestrictively late. This paper (Part II) considers the problem of minimizing the unweighted earliness and tardiness of...

  • OPTIMIZING OVER THE EFFICIENT SET USING A TOP-DOWN SEARCH OF FACES. Sayin, Serpil // Operations Research;Jan/Feb2000, Vol. 48 Issue 1, p65 

    The problem of optimizing a linear function over the efficient set of multiple objective linear programming problem is studied. The decomposition of the efficient faces is used as the basis of a search-based algorithm to solve this problem. The faces of the feasible region are characterized by...

  • ECONOMIC LOT SIZE DETERMINATION IN MULTI-STAGE ASSEMBLY SYSTEMS. Crowston, Wallace B.; Wagner, Michael; Williams, Jack F. // Management Science;Jan1973, Vol. 19 Issue 5, p517 

    We consider the optimal lot size problem for multi-stage assembly systems where each facility may have many predecessors but only a single successor. Assumptions include constant continuous final product demand, instantaneous production, and an infinite planning horizon. Costs at each facility...

  • Maximization Problems in Single Machine Scheduling. Aloulou, Mohamed Ali; Kovalyov, Mikhail Y.; Portmann, Marie-Claude // Annals of Operations Research;Jul2004, Vol. 129 Issue 1-4, p21 

    Problems of scheduling n jobs on a single machine to maximize regular objective functions are studied. Precedence constraints may be given on the set of jobs and the jobs may have different release times. Schedules of interest are only those for which the jobs cannot be shifted to start earlier...

  • Feature Based Dense Stereo Matching using Dynamic Programming and Color. Sadeghi, Hajar; Moallem, Payman; Monadjemi, S. Amirhassn // International Journal of Computational Intelligence;2008, Vol. 4 Issue 3, p179 

    This paper presents a new feature based dense stereo matching algorithm to obtain the dense disparity map via dynamic programming. After extraction of some proper features, we use some matching constraints such as epipolar line, disparity limit, ordering and limit of directional derivative of...

  • CONVERGENCE CONDITIONS FOR NONLINEAR PROGRAMMING ALGORITHMS. Zangwill, Willard I. // Management Science;Sep69, Vol. 16 Issue 1, p1 

    Conditions which are necessary and sufficient for convergence of a nonlinear programming algorithm are stated. It is also shown that the convergence conditions can be easily applied to most programming algorithms. As examples, algorithms by Arrow, Hurwicz and Uzawa; Cauchy; Frank and Wolfe; and...

  • A NOTE ON DUALITY THEOREM FOR A NONLINEAR PROGRAMMING PROBLEM. Bhatia, Davinder // Management Science;May70, Vol. 16 Issue 9, p604 

    S. M. Sinha has formulated a stochastic linear programming problem as a deterministic non linear program, and has shown how to solve this program by solving its dual [1]. Our note extends Sinha's result, by dropping the restriction that the primal constraint set be bounded, and simplifies some...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

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

Try another library?
Sign out of this library

Other Topics