Dondet, V. R.; Emmons, Hamilton
January 1992
Operations Research;Jan/Feb92 Supplement 1, Vol. 40 Issue 1, p76
Academic Journal
We consider a scheduling problem that involves two types of processors, but three types of jobs. Each job has a fixed start time and a fixed completion time, and falls into one of three types. Jobs of type 1 can be done only by type-1 processors, type-2 jobs only by type-2 processors, and type-0 jobs by either type of processors. We present a polynomial algorithm for finding the minimal cost combination of the two types of processors required to complete all jobs. The steps of the algorithm consist of constructing a job schedule network, transforming it into a single-commodity flow problem and finding the maximal flow through it.


Related Articles

  • Generalized Covering Relaxation for 0-1 Programs. Granot, Daniel; ranot, Frieda // Operations Research;Nov/Dec80, Vol. 28 Issue 6, p1442 

    We construct in this paper a general purpose cutting-plane algorithm for solving the 0-1 polynomial programming problem of finding a 0-1 n vector x = (x[sub j]) that maximizes c[sup T]x subject to f(x) is less than or equal to b where f(x) = (f,(x)) is an m vector of polynomials. The algorithm...

  • C.P.M. SCHEDULING WITH SMALL COMMUNICATION DELAYS AND TASK DUPLICATION. Colin, J. Y.; Chr├ętienne, P. // Operations Research;Jul/Aug91, Vol. 39 Issue 4, p680 

    This paper addresses a machine scheduling problem that arises in the case of scheduling tasks over an idealized distributed multiprocessor. Precedence constraints with small communication delays have to be taken into account and task duplication is allowed. A critical path-like algorithm is...

  • On Scheduling Independent Tasks with Restricted Execution Times. Leung, Joseph Y-T. // Operations Research;Jan/Feb82, Vol. 30 Issue 1, p163 

    We consider the problem of nonpreemptively scheduling n independent tasks on m identical and parallel machines with the objective of minimizing the overall finishing time. The problem has been shown to be NP-complete in the strong sense and hence there probably will not be any pseudopolynomial...

  • ON THE EXACT UPPER BOUND FOR THE MULTIFIT PROCESSOR SCHEDULING ALGORITHM. Minyi Yue // Annals of Operations Research;1990, Vol. 24 Issue 1-4, p233 

    We consider the well-known problem of scheduling n independent tasks nonpreemptively on m identical processors with the aim of minimizing the makespan. Coffman, Garey and Johnson [1] described an algorithm, MULTIFTT, based on techniques from bin-packing, with better worst performance than the...

  • A NEW ALGORITHM FOR THE QUASI-ASSIGNMENT PROBLEM. Tiantai Song; Li Zhou // Annals of Operations Research;1990, Vol. 24 Issue 1-4, p205 

    The quasi-assignment problem can be used to solve the bus scheduling problem, the tourist guide problem, and the minimum number of chains in a partially ordered set. A successive shortest path algorithm for the assignment problem is extended to the quasi-assignment problem. The algorithm is a...

  • APPROXIMATION ALGORITHMS FOR FIXED JOB SCHEDULE PROBLEMS. Fischetti, Matteo; Martello, Silvano; Toth, Paolo // Operations Research;Jan/Feb92 Supplement 1, Vol. 40 Issue 1, p96 

    We consider two generalizations of the fixed job schedule problem, obtained by imposing a bound on the spread-time or on the working time of each processor. These NP-hard problems, studied by the authors in previous works, can arise in bus driver scheduling. We introduce several polynomial-time...

  • Single-machine scheduling with both deterioration and learning effects. Dar-Li Yang; Wen-Hung Kuo // Annals of Operations Research;Nov2009, Vol. 172 Issue 1, p315 

    This paper considers a single-machine scheduling problem with both deterioration and learning effects. The objectives are to respectively minimize the makespan, the total completion times, the sum of weighted completion times, the sum of the kth power of the job completion times, the maximum...

  • Heuristic-Programming Solution of a Flowshop-Scheduling Problem. Krone, Martin J.; Steiglitz, Kenneth // Operations Research;May/Jun74, Vol. 22 Issue 3, p629 

    This paper considers the static flowshop-scheduling problem with the objective of minimizing, as a cost function, the mean job-completion time. Within the more general framework of combinatorial optimization problems, it defines a heuristic search technique--an approach that has been successful...

  • Minimizing maximum absolute lateness and range of lateness under generalized due dates on a single machine. Tanaka, Keisuke; Vlach, Milan // Annals of Operations Research;1999, Vol. 86 Issue 1-4, p507 

    We investigate the problems of minimizing the maximum absolute lateness and range of lateness under generalized due dates on a single machine. In contrast to the traditional due date cases, we show that these problems are unary NP-hard. Furthermore, we present simple approximation algorithms for...


Read the Article


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

Try another library?
Sign out of this library

Other Topics