A state-of-the-art review of parallel-machine scheduling research
European Journal of Operational ResearchPublished 1 August 1990
T.C.E. Cheng, C.C.S. Sin
Citations507
SJR quartileQ1
SJR score2.24
SNIP2.62
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The major research results in deterministic parallel-machine scheduling theory will pass a survey and it is revealed that there exist a lot of potential areas worthy of further research.
Abstract
In this paper the major research results in deterministic parallel-machine scheduling theory will pass a survey. The review reveals that there exist a lot of potential areas worthy of further research.
Keywords
Computer ScienceEngineering
Reducibility among Combinatorial Problems
10,823 Citations1972Richard M. Karp
Annals of discrete mathematicsOptimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
5,791 Citations1979Ronald Graham, Eugene L. Lawler +2 more
The state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory are surveyed.
Operational Research Quarterly (1970-1977)Introduction to Sequencing and Scheduling
2,619 Citations1977A. J. Clewett, Kenneth R. Baker
SIAM Journal on Applied MathematicsBounds on Multiprocessing Timing Anomalies
2,342 Citations1969Ron Graham
Annals of discrete mathematicsComplexity of Machine Scheduling Problems
2,148 Citations1977Jan Karel Lenstra, A. H. G. Rinnooy Kan +1 more
A classification of scheduling problems on single, different and identical machines is given and NP-completeness is established for a large number of other machine scheduling problems.
Bell System Technical JournalBounds for Certain Multiprocessing Anomalies
1,617 Citations1966Ronald Graham
Journal of Computer and System SciencesNP-complete scheduling problems
1,429 Citations1975Jeffrey D. Ullman
It is shown that the problem of finding an optimal schedule for a set of jobs is NP-complete even in the following two restricted cases, tantamount to showing that the scheduling problems mentioned are intractable.
Operations ResearchA Survey of Scheduling Rules
1,295 Citations1977S. S. Panwalkar, Wafik H. Iskander
This paper presents a summary of over 100 priority dispatching rules, a list of many references that analyze them, and a classification scheme.
Journal of the Operational Research SocietySequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop
1,004 Citations1982Graham K. Rand, Simon French
Operations ResearchParallel Sequencing and Assembly Line Problems
895 Citations1961T. C. Hu
This paper deals with a new sequencing problem in which n jobs with ordering restrictions have to be done by men of equal ability, and how to arrange a schedule that requires the minimum number of men to complete all jobs within a prescribed time T.
Management ScienceScheduling with Deadlines and Loss Functions
846 Citations1959Robert McNaughton
The problem of this paper is that of scheduling several one-stage tasks on several processors, which are capable of handling the tasks with varying degrees of efficiency, to minimize the total loss, which is a sum of losses associated with the individual tasks.
Journal of the ACMUsing dual approximation algorithms for scheduling problems theoretical and practical results
779 Citations1987Dorit S. Hochbaum, David B. Shmoys
A new approach to constructing approximation algorithms, which the aim is find superoptimal, but infeasible solutions, and the performance is measured by the degree of infeasibility allowed, which should find wide applicability for any optimization problem where traditional approximation algorithms have been particularly elusive.
NetworksOn the Computational Complexity of Combinatorial Problems
712 Citations1975Richard M. Karp
A large class of classical combinatorial problems, including most of the difficult problems in the literature of network flows and computational graph theory, are shown to be equivalent, in the sense that either all or none of them can be solved in polynomial time.
SIAM Journal on ComputingAn Application of Bin-Packing to Multiprocessor Scheduling
657 Citations1978E. G. Coffman, M. R. Garey +1 more
This work considers one of the basic, well-studied problems of scheduling theory, that of nonpreemptively scheduling n independent tasks on m identical, parallel processors with the objective of minimizing the number of overlapping tasks.
Acta InformaticaOptimal scheduling for two-processor systems
610 Citations1972E. G. Coffman, Ronald Graham
It is proved that the algorithm gives optimal solutions and its application to preemptive scheduling disciplines is discussed.
Journal of the ACMAlgorithms for Scheduling Independent Tasks
593 Citations1976Sartaj Sahni
Three general techniques are presented to obtain approximate solutions for optimization problems solvable in this way, and polynomial time algorithms are applied to obtain “good” approximate solutions.
DSpace@MIT (Massachusetts Institute of Technology)Near-optimal bin packing algorithms
566 Citations1973David S. Johnson
Communications of the ACMScheduling independent tasks to reduce mean finishing time
500 Citations1974John Bruno, E. G. Coffman +1 more
It is shown that the most general mean-finishing-time problem for independent tasks is polynomial complete, and hence unlikely to admit of a non-enumerative solution.
Medical Entomology and ZoologyMachine Scheduling Problems: Classification, complexity and computations
478 Citations1976Rinnooy Kan
The algorithm of McMahon and Florian 62, a branch-and-bound algorithm for solving the n|1|ri0|cmax problem, shows promise in solving the two-Machine and Three-Machine problems.
Management ScienceA Functional Equation and its Application to Resource Allocation and Sequencing Problems
413 Citations1969Eugene L. Lawler, Joann Moore
European Journal of Operational ResearchMachine scheduling problems: Classification, complexity and computations
342 Citations1977Graham K. Rand
Recent Developments in Deterministic Sequencing and Scheduling: A Survey
318 Citations1982Eugene L. Lawler, Jan Karel Lenstra +1 more
The state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory are surveyed.
Journal of the ACMOn Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
271 Citations1978Eugene L. Lawler, Jacques Labetoulle
It is shown that no more than O(m 2) preemptions are necessary, in order to schedule n jobs on m unrelated processors so as to minimize makespan.
Journal of the Royal Statistical Society Series C (Applied Statistics)Introduction to the Design and Analysis of Algorithms.
253 Citations1979Tony Greenfield, S. E. Goodman +1 more
An introduction to the Design and Analysis of Algorithms and its applications to computer science.
European Journal of Operational ResearchSolving a bicriterion scheduling problem
236 Citations1980L. N. Van Wassenhove, Ludo Gelders
A pseudo-polynomial algorithm is given to enumerate all these efficient points to minimize the holding cost and the maximum tardiness of n jobs to be sequenced on a single machine.
Management ScienceScheduling Independent Tasks on Parallel Processors
218 Citations1966Michael H. Rothkopf
An optimal scheduling rule is presented for the single processor scheduling of tasks with continuously discounted linear waiting costs and a dynamic programming algorithm has been developed for a wide class of parallel-processor problems.
ACM Computing SurveysDeterministic Processor Scheduling
216 Citations1977Mario J. Gonzalez
This paper surveys the deterministic scheduling of jobs in job-shop and multIprogramming environments, flow-shop schedules, and multiprocessor schedules in terms of optimal constructive algorithms and suboptimal heuristics.
SIAM Journal on Applied MathematicsOptimal Sequencing of Two Equivalent Processors
186 Citations1969M. Fujii, Tadao Kasami +1 more
This paper presents an efficient algorithm for a class of sequencing problems in which n tasks with an arbitrary precedence relation have to be processed by two processors of equal ability, and each task requires one unit of time.
Journal of the Operational Research SocietyDeterministic and Stochastic Scheduling
179 Citations1983Kevin Mahon
When you read more every page of this deterministic and stochastic scheduling, what you will obtain is something great.
European Journal of Operational ResearchA bicriterion approach to time/cost trade-offs in sequencing
167 Citations1982Luk N. Van Wassenhove, Kenneth R. Baker
Management ScienceBounds for the Optimal Scheduling of <i>n</i> Jobs on <i>m</i> Processors
158 Citations1964Willard L. Eastman, Shimon Even +1 more
Lower and upper bounds are given for the cost of an optimal schedule and a procedure is described for obtaining a schedule which costs less than the given upper bound.
Journal of the ACMScheduling Tasks with Nonuniform Deadlines on Two Processors
150 Citations1976M. R. Garey, David S. Johnson
It is shown that the problem of finding a one-processor schedule which minimizes the number of tasks failing to meet their deadlines is NP-complete and, hence, is likely to be computationally intractable.
Journal of the ACMA Level Algorithm for Preemptive Scheduling
147 Citations1977Edward C. Horvath, Shui Lam +1 more
A level algorithm is given that constructs optimal preemptive schedules on identical processors when the task system is a tree or when there are only two processors available, and an upper bound on its performance is derived in terms of the speeds of the processors.
Operations ResearchTechnical Note—Minimizing Average Flow Time with Parallel Machines
144 Citations1973W. A. Horn
The assignment and sequencing of single-operation jobs in a parallel-machine environment can be formulated as an assignment problem and means for reducing the size and computational difficulty of this problem are identified.
BIT Numerical MathematicsA linear time approximation algorithm for multiprocessor scheduling
129 Citations1979Greg Finn, Ellis Horowitz
AnO(n) approximation algorithm is presented which tries to determine a nonpreemptive schedule with minimum finish time and extensive empirical results show that the new algorithm is competitive with the LPT algorithm in terms of quality of solution and faster interms of computing time.
SIAM Journal on ComputingTighter Bounds for the Multifit Processor Scheduling Algorithm
122 Citations1984Donald K. Friesen
This paper considers the problem of nonpreemptively scheduling n independent jobs on m identical, parallel processors with the object of minimizing the “makespan”, or completion time for the entire processor, with the aim of minimize the "makespan" of the entire system.
Journal of the ACMAnalysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
122 Citations1975K. L. Krause, V. Y. Shen +1 more
An abstract system model which consists of several identical and independent task processors and a memory of arbitrary size is presented and a new heuristic algorithm is introduced which is shown to be better in many cases than the simpler algorithms when the worst-case performance bounds are compared.
Operations ResearchGeneral Techniques for Combinatorial Approximation
121 Citations1977Sartaj Sahni
This is a tutorial on general techniques for combinatorial approximation, which generate fully polynomial time approximation schemes for a large number of NP-complete problems.
IEEE Transactions on ComputersOptimal Preemptive Scheduling on Two-Processor Systems
120 Citations1969Richard R. Muntz, E. G. Coffman
This paper considers the static scheduling of computations for a system containing two indentical processors and a solution for the two-machine case with preemptive scheduling is presented.
SIAM Journal on Algebraic and Discrete MethodsScheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
117 Citations1982Bryan L. Deuermeyer, Donald K. Friesen +1 more
This investigation considers the problem of nonpreemptively assigning a set of independent tasks to a system of identical processors to maximize the earliest processor finishing time and proves that the worst-case performance of the LPT algorithm has an asymptotically tight bound of $4}{3}$ times the optimal.
OmegaSingle machine scheduling research
116 Citations1987Sushil Gupta, Jerzy Kyparisis
This paper reviews static scheduling research on single machine for the last three decades after an extensive search in the English language periodicals and reveals several interesting facts about the developments in single machine scheduling research and its future.
Mathematics of Operations ResearchScheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
107 Citations1977Peter Brucker, M. R. Garey +1 more
This work considers an extension of this special case model to include the possibility of individual task deadlines, in which case the goal is to minimize maximum lateness and shows that it makes a considerable difference whether the precedence is of “in-tree” or “out- tree” form.
Journal of the ACMAn Almost-Linear Algorithm for Two-Processor Scheduling
105 Citations1982Harold N. Gabow
An o(e+nalpha(n)) algorithm is presented which is based on the idea of a highest-level-first (hlf) schedule which always executes nodes on the longest paths of the precedence dag.
European Journal of Operational ResearchCombinatorial optimization algorithm and complexity
103 Citations1983Antoon Kolen
OmegaBicriterion static scheduling research for a single machine
100 Citations1988Parthasarati Dileepan, Tapan Sen
A critical review of the single machine static scheduling problem with two criteria jointly with a joint objective function where both criteria are included is presented.
Deterministic and Stochastic Scheduling
93 Citations1982M. A. H. Dempster, J. K. Lenstra +1 more
SIAM Journal on ComputingWorst Case Analysis of Two Scheduling Algorithms
91 Citations1977Shui Lam, Ravi Sethi
It is shown that the ratio of the lengths of their algorithm and an optimal schedule is bounded by $2 - 2/m$ and in both the nonpreemptive and the preemptive cases there exist task systems for which the ratio can be approached arbitrarily closely.
SIAM Journal on ComputingScheduling Independent Tasks on Uniform Processors
89 Citations1984Gregory Dobson
A worst-case analysis is given for the LPT (longest processing time) heuristic applied to the problem of scheduling independent tasks on uniform processors and tight bounds are derived for the ratio of the heuristic to the optimal makespan.
Operations ResearchPreemptive Scheduling with Due Dates
85 Citations1979Sartaj Sahni
An 0(n log mn) algorithm is presented to preemptively schedule n tasks on m identical machines that meets all due dates (when possible) and generates schedules with at most n − 2 preemptions.
SIAM Journal on Algebraic and Discrete MethodsScheduling Opposing Forests
81 Citations1983M. R. Garey, David S. Johnson +2 more
It is shown that a polynomial time algorithm for a wider class of precedence constraints is unlikely, and it is proved that the problem to be NP-complete for precedence constraints that are the disjoint union of an in-forest and an out-forest (the “opposing forests” of the title).
European Journal of Operational ResearchNew trends in machine scheduling
80 Citations1988Jacek Błażewicz, Gerd Finke +2 more
This review is concerned with new directions in deterministic machine scheduling theory, studying resource constrained scheduling, scheduling tasks that require more than one machine at a time, scheduling with nonlinear speed-resource alloted functions, and scheduling in flexible manufacturing systems.
SIAM Journal on ComputingScheduling Graphs on Two Processors
75 Citations1976Ravi Sethi
Coffman and Graham give an algorithm for determining nonpreemptive schedules on two processors for such systems as directed acyclic graph (dag) D with n nodes and e edges.
Management ScienceEvaluation of a Heuristic for Scheduling Independent Jobs on Parallel Identical Processors
73 Citations1979Ali Dogramaci, Julius Surkis
The study reported in this paper focuses on a heuristic which can handle reasonably large problems, and yet can be simply and economically implemented.
A I I E TransactionsAn Improved Algorithm for Scheduling Jobs on Identical Machines
71 Citations1977J. Wesley Barnes, J.J. Brennan
The improved algorithm is based upon the technique of Elmaghraby and Park and is the result of three theoretical refinements of their basic method in conjunction with newly developed results.
SIAM Journal on ComputingBounds for Multifit Scheduling on Uniform Processors
62 Citations1983Donald K. Friesen, Michael A. Langston
A variation of the MULTIFIT algorithm derived from bin packing is analyzed, and it is proved that its worst-case performance bound is within 1.4 of the optimum.
Management ScienceScheduling with Deadlines and Loss Functions on <i>k</i> Parallel Machines
62 Citations1965James G. Root
An optimal schedule is developed for H jobs on K identical machines in single stage production that minimizes ∑b[max (0, Ai − di)] where Ai is the actual completion time forJob i and di is the deadline for job i.
A generalized bound on LPT sequencing
61 Citations1976E. G. Coffman, Ravi Sethi
Graham's result is generalized so as to include a parameter characterizing the number of tasks assigned to processors by the LPT rule, and the new result will show that the worst-case performance bound for LPT sequencing approaches unity approximately as 1+1/k.
Mathematics of Operations ResearchThe Asymptotic Optimality of the LPT Rule
60 Citations1987J. B. G. Frenk, A. H. G. Rinnooy Kan
Under mild conditions on the probability distribution, strong asymptotic optimality results are obtained for the LPT Longest Processing Time rule, in which the jobs are assigned to the machines in order of nonincreasing processing requirements.
IEEE Transactions on ComputersAn Almost-Optimal Algorithm for the Assembly Line Scheduling Problem
56 Citations1974Marc T. Kaufman
A solution to the multiprocessor scheduling problem for the case where the ordering relation between tasks can be represented as a tree is considered, and the "longest path" scheduling method is almost-optimal in the following sense.
Mathematics of Operations ResearchOn the Complexity of Mean Flow Time Scheduling
55 Citations1977Ravi Sethi
It is shown that on two or more machines, the problem is NP-complete even if the precedence constraints are tree-like, and this work proves the result both for in-trees in which the root is the last task to be processed, and out-Trees inWhich theroot is the first task to being processed.
Journal of the Operational Research SocietyA Heuristic for Common Due-date Assignment and Job Scheduling on Parallel Machines
52 Citations1989T.C.E. Cheng
It is shown that the optimal job sequence for the single-machine problem can be easily determined, and it is proved that the same optimal due-date result can be generalized to the parallel- machine problem.
International Journal of Production ResearchSome ways to increase flexibility in manufacturing systems
51 Citations1985R. MURAMATSU, Kazuyoshi� Ishii +1 more
Management ScienceGeometric Approaches to Solving the Traveling Salesman Problem
50 Citations1977John P. Norback, Robert F. Love
Two geometric approaches to solving sequencing problems are described and tested, and the largest angle method can be used to generate tours without any computation, giving the practitioner an effective "back of the envelope method" of finding solutions.
International Journal of Production ResearchAn improved branching scheme for the branch and bound procedure of scheduling<i>n</i>jobs on<i>m</i>parallel machines to minimize total weighted flowtime
48 Citations1988Subhash C. Sarin, Seokyoo Ahn +1 more
A branching scheme different from theirs is proposed and shows its superiority and some new and simple results are presented which are easy to implement to obtain an efficient branch-and-bound algorithm.
Decision SciencesSCHEDULING TO MINIMIZE MAKESPAN ON UNEQUAL PARALLEL PROCESSORS
46 Citations1980Prabuddha De, Thomas E. Morton
A new heuristic is devised that, although the heuristic takes negligible time compared to the branch-and-bound procedure, on the average it is within 5 percent of the latter in the uniform case and within 1.3 percent in the general case.
Journal of the ACMA New Algorithm for Preemptive Scheduling of Trees
46 Citations1980Teofilo F. Gonzalez, D. Barton Johnson
A simpler algorithm which runs in O(nm) time on the same problem and can be adapted to give optimal finish time schedules on-line for independent tasks with release times.
Management ScienceNote—A Branch-and-Bound Approach to the Bicriterion Scheduling Problem Involving Total Flowtime and Range of Lateness
45 Citations1988Tapan Sen, Farhad M. E. Raiszadeh +1 more
Operations ResearchOn Scheduling Independent Tasks with Restricted Execution Times
42 Citations1982Joseph Y.‐T. Leung
It is shown that if the execution times are restricted to a fixed number, say k, of different values, then the problem of nonpreemptively scheduling n independent tasks on m identical and parallel machines can be solved in polynomial time.
Operations ResearchLinear-Time Algorithms for Scheduling on Parallel Processors
41 Citations1982Clyde Monma
Linear-time algorithms are presented for several problems of scheduling n equal-length tasks on m identical parallel processors subject to precedence constraints, which improves upon previous time bounds for the maximum lateness problem with treelike precedence constraints.
Naval Research Logistics QuarterlyScheduling with parallel processors and linear delay costs
41 Citations1973Kenneth R. Baker, Alan G. Merten
The theoretical properties of this m-machine problem are explored, and the problem of determining an optimum scheduling procedure is examined; properties of the optimum schedule are given as well as the corresponding reductions in the number of schedules that must be evaluated in the search for an optimum.
Acta InformaticaProbabilistic bounds for dual bin-packing
36 Citations1985JohnL. Bruno, PeterJ. Downey
The first fit increasing heuristic is studied, which shows that the performance of the FFI policy can be made arbitrarily close to that of the optimal policy with any desired degree of confidence, for large sample sizes.
SIAM Journal on ComputingCombinatorial Analysis of an Efficient Algorithm for Processor and Storage Allocation
35 Citations1979E. G. Coffman, Joseph Y.‐T. Leung
An $NP$-complete bin-packing problem is studied, and an efficient approximation algorithm is defined and studied, with main results are bounds on the complexity of the algorithm and on its performance.
Operations ResearchOn the Expected Relative Performance of List Scheduling
35 Citations1985E. G. Coffman, E. N. Gilbert
Reordering the tasks in an optimal way can reduce the makespan to OPTXI, the smallest possible makespan, but requires knowing the Xi in advance and solving an NP-complete problem.
Lecture notes in computer scienceOn a class of scheduling algorithms for multiprocessors computing systems
34 Citations1975Nana Chen, Chunxiao Liu
This paper studies a class of scheduling algorithms for multiprocessors computing systems which are simple and easy to implement and produces optimal schedules in some cases, and close-to-optimal schedules in other cases.
SIAM Journal on ComputingNonpreemptive LP-Scheduling on Homogeneous Multiprocessor Systems
33 Citations1981Manfred Kunde
Worst-case bounds for the ratio of the length of an LP-schedule and an optimal schedule are given for two classes of dependency structures—chains and trees and for anti-tree-systems.
Mathematics of Operations ResearchA Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors
30 Citations1984E. G. Coffman, Greg N. Frederickson +1 more
It is proved that the expected makespan for LF is bounded by n4 and for RLF it is precisely n4, and a lower bound on expected LF makespans is shown to be $$\frac{n}4 + \frac{1}{4n+1}.$$
Management ScienceParallel Machine Scheduling: Processing Rates Dependent on Number of Jobs in Operation
30 Citations1987Moshe Dror, Helman I. Stern +1 more
This paper treats the class of n job - m machine scheduling problems with job processing times dependent on the number of jobs being simultaneously processed in the system at any point in time, and finds the makespan is found to be independent of the job-machine assignment.
SIAM Journal on Applied MathematicsErratum “Optimal Sequencing of Two Equivalent Processors”
28 Citations1971M. Fujii, Tadao Kasami +1 more
Mathematics of Operations ResearchTight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling
28 Citations1984Richard Loulou
The partitioning problem is studied, consisting in partitioning a sublist of n positive numbers into m disjoint sublists such that the maximum sublist is minimized, which is equivalent to minimizing the completion time of n jobs on m parallel identical processors.
Discrete Applied MathematicsThe rate of convergence to optimality of the LPT rule
27 Citations1986J. B. G. Frenk, A. H. G. Rinnooy Kan
Fast allocation algorithms
27 Citations1972D. S. Johnson
An improved polynomial-time algorithm is found for a problem of scheduling on multiprocessing systems, by treating this as a bin packing problem.
SIAM Journal on ComputingMinimum Delay Codes
21 Citations1989Lawrence L. Larmore
Huffman's algorithm finds a prefix-free binary code on a weighted alphabet which minimizes the expected length of the code string for a single symbol, and it is conjectured that the algorithm has substantially lower time and space complexities in the worst case, and still lower in the average case.
On the rate of convergence to optimality of the LPT rule
18 Citations2011A. H. G. Rinnooy Kan, J. B. G. Frenk
Probabilistic Analysis of the LPT Processor Scheduling Heuristic
15 Citations1982E. G. Coffman, Greg N. Frederickson +1 more
The average performance of the LPT processor scheduling algorithm is analyzed, under the assumption that task times are drawn from a uniform distribution on (0,1].
Journal of the ACMBounds on Schedules for Independent Tasks with Similar Execution Times
10 Citations1981James O. Achugbue, Francis Y. L. Chin
An open problem by Graham is solved of scheduling a set of n independent tasks nonpreemptively on m identical processors to minimize finish time.
International Journal of Production ResearchAn algorithm for scheduling parallel processors
9 Citations1975Mabaran Rajaraman
An algorithm for determining the optimal schedule of jobs on identical parallel processors is developed and a proof of the algorithm is given which indicates the effectiveness of the algorithms as compared to complete enumeration.
An Introduction to Proof Techniques for Bin-Packing Approximation Algorithms
8 Citations1982E. G. Coffman
The aim in this brief tutorial extension of the survey in [GJ] will be to explain somewhat informally certain techniques that do enjoy a moderately broad applicability, while making it clear where the novelty and perhaps ingenuity of the approach to an individual problem may be required.
Journal of CyberneticsOn Two—Processor Scheduling of One— or Two—Unit Time Tasks with Precedence Constraints
7 Citations1975Óscar H. Ibarra, Chul E. Kim
It is shown that LPTS produces a schedule with an error where f * and f are the finish times of an optimal and LPTS schedules, respectively, and a comparison of the LPTS algorithm with other scheduling algorithms is presented.
RACO (Revistes Catalanes amb Accés Obert) (Consorci de Serveis Universitaris de Catalunya)An Introduction To Multiprocessor Scheduling
6 Citations1980Jan Karel Lenstra, A. H. G. Rinnooy Kan
This is a tutorial survey of recent results in the area of multiprocessor scheduling that involves the development of new polynomial optimization algorithms and the application of the concept of NP-hardness as well as the analysis of approximation algorithms.
Computers & Operations ResearchPerformance of the LPT algorithm in multiprocessor scheduling
6 Citations1990Tien Yuan Kao, Elsayed A. Elsayed
A stochastic model is studied which shows that if Ti's are order statistics of n draws from the uniform distributed interval [0, 1], then ∀1, E[V 1 ]+⩽ m(m−1) 2(n+1) , where E[Vi]+ is an upper bound of the expected system idle time with respect to job i.
Naval Research Logistics QuarterlyA parallel sequencing algorithm for minimizing total cost
5 Citations1977Mabaran Rajaraman
The proposed algorithm finds the sequence (or sequences) with minimum total cost (sum of waiting, penalty and processor costs) when jobs have different available times, due dates, penalty costs and waiting costs.
Naval Research Logistics QuarterlyHu's precedence tree scheduling algorithm: A simple proof
5 Citations1984James A. M. McHugh
A simple proof of Hu's algorithm for scheduling in minimum time a set of tasks constrained by precedence tree constraints, each task requiring a unit time to complete, and where m processors are available is presented.
AgEcon Search (University of Minnesota, USA)AN INTRODUCTION TO MULTIPROCESSOR SCHEDULING
2 Citations1980Jan Karel Lenstra, A. H. G. Rinnooy Kan +2 more
…