Minimizing maximum absolute lateness and range of lateness under generalized due dates on a single machine

Tanaka, Keisuke; Vlach, Milan
March 1999
Annals of Operations Research;1999, Vol. 86 Issue 1-4, p507
Academic Journal
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 these problems, and show that they achieve the performance ratios of n for the problem of minimizing the maximum absolute lateness and of ⌈n/2 ⌉ for the problem of minimizing the range of lateness, where ⌈x⌉ is the smallest integer no less than x.


Related Articles

  • An iterative algorithm for scheduling unit-time tasks with precedence constraints to minimise the maximum lateness. Zinder, Yakov; Roper, Duncan // Annals of Operations Research;1998, Vol. 81 Issue 1-4, p321 

    We consider the maximum lateness problem in which all tasks have the same execution time and must be processed on m » 1 parallel identical processors subject to precedence constraints. All tasks and all processors are available at time t = 0, and each task has a due date. If all due dates are...

  • 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 note on asymptotic formulae for one-dimensional network flow problems. Daganzo, Carlos F.; Smilowitz, Karen R. // Annals of Operations Research;Jun2006, Vol. 144 Issue 1, p153 

    This note develops asymptotic formulae for single-commodity network flow problems with random inputs. The transportation linear programming problem (TLP) where N points lie in a region of R1 is one example. It is found that the average distance traveled by an item in the TLP increases with N1/2;...

  • PREEMPTIVE SCHEDULING OF EQUAL LENGTH JOBS ON TOW MACHINES TO MINIMIZE MEAN FLOW TIME. Herrbach, Lee A.; Leung, Joseph Y.-T. // Operations Research;May/Jun90, Vol. 38 Issue 3, p487 

    We give an O(n log n) time algorithm to preemptively schedule n equal-length jobs with release times on two identical, parallel machines so as to minimize the mean flow time. The complexity of the general problem of minimizing the mean weighted flow time is also reviewed, both for nonpreemptive...

  • Simultaneous Job Scheduling and Resource Allocation on Parallel Machines. Zhi-Long Chen // Annals of Operations Research;Jul2004, Vol. 129 Issue 1-4, p135 

    Most deterministic production scheduling models assume that the processing time of a job on a machine is fixed externally and known in advance of scheduling. However, in most realistic situations, apart from the machines, it requires additional resources to process jobs, and the processing time...

  • A scheduling algorithm for the reentrant shop: an application in semiconductor manufacture. Yong-Ha Kang; Sung-Shick Kim; Hyun Joo Shin // International Journal of Advanced Manufacturing Technology;Dec2007, Vol. 35 Issue 5/6, p566 

    This paper addresses a heuristic algorithm that minimizes total weighted tardiness for reentrant flow shop problems with sequence-dependent set up time. The proposed algorithm consists of three phases: prior plan phase, initial solution generation phase and solution improvement phase. In the...

  • MINIMIZING VARIATION OF FLOW TIME IN SINGLE MACHINE SYSTEMS. Kanet, John J. // Management Science;Dec1981, Vol. 27 Issue 12, p1453 

    This paper addresses the problem of n jobs to be scheduled on a single machine in such a way that flow time variation is minimized. When the measure of variation is total absolute difference of completion times (TADC) the problem is shown to be quite simple. Sufficient conditions are shown for...

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


Read the Article


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

Try another library?
Sign out of this library

Other Topics