Minyi Yue
June 1990
Annals of Operations Research;1990, Vol. 24 Issue 1-4, p233
Academic Journal
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 LPT algorithm and proved that it satisfies a bound of 1.22. It has been claimed by Friesen [2] that this bound can be improved upon to 1.2. However, we found his proof, in particular his lemma 4.9, difficult to understand. Yue, Kellerer and Yu [3] have presented the bound 1.2 in a simpler way. In this paper, we prove first that the bound cannot exceed 13/11 and then prove that it is exactly 13/11.


Related Articles

  • OPTIMAL PRODUCTION SCHEDULES FOR FLOW SHOPS. McMahon, G. B. // CORS Journal;Jul69, Vol. 7 Issue 2, p141 

    An approach to the flow-shop scheduling problem introduced by Dudek and Teuton has been modified by Smith and Dudek and by Bagga and Chakravarti. This paper presents a comprehensive theory for this approach and improves on the results obtained in these earlier papers. It also shows how 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...

  • Nonstrict vector summation in multi-operation scheduling. Sevastianov, Sergey // Annals of Operations Research;1998, Vol. 83 Issue 1-4, p179 

    We consider several multi-operation scheduling problems with m machines and n jobs, including flow shop, open shop, assembly line, and a few special cases of job shop with the minimum makespan criterion. It is demonstrated that the problems in question can be efficiently solved by approximation...

  • 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...

  • BATCH SIZING AND JOB SEQUENCING ON A SINGLE MACHINE. Coffman Jr., E. G.; Yannakakis, M.; Magazine, M. J.; Santos, C. // Annals of Operations Research;1990, Vol. 26 Issue 1-4, p135 

    We study a single-machine scheduling problem in which the items to be processed have lo be batched as well as sequenced. Since processed items become available in batches, flow times are defined to be the same for all items in the same batch. A constant set-up delay is incurred between...

  • Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors. Bianco, L.; Blazewicz, J.; Dell'Olmo, P.; Drozdowski, M. // Annals of Operations Research;1995, Vol. 58 Issue 1-4, p493 

    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...

  • 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...

  • An immune algorithm approach to the scheduling of a flexible PCB flow shop. Alisantoso, D.; Khoo, L. P.; Jiang, P. Y. // International Journal of Advanced Manufacturing Technology;Dec2003, Vol. 22 Issue 11/12, p819 

    Scheduling is an important task in manufacturing. It involves assigning jobs to machines in a particular order so as to meet the manufacturing target. With the increase in manufacturing complexity, conventional scheduling techniques for generating a reasonable manufacturing schedule have become...

  • Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem. Panwalkar, S. S.; Smith, M. L.; Seidmann, A. // Operations Research;Mar/Apr82, Vol. 30 Issue 2, p391 

    We consider an n job, one machine scheduling problem in which all jobs have a common due date. The objective is to determine the optimal value of this due date and an optimal sequence to minimize a total penalty function. This penalty function is based on the due date value and on the earliness...


Read the Article


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

Try another library?
Sign out of this library

Other Topics