TITLE

Maximization Problems in Single Machine Scheduling

AUTHOR(S)
Aloulou, Mohamed Ali; Kovalyov, Mikhail Y.; Portmann, Marie-Claude
PUB. DATE
July 2004
SOURCE
Annals of Operations Research;Jul2004, Vol. 129 Issue 1-4, p21
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
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 without changing job sequence or violating release times or precedence constraints. Solutions to the maximization problems provide an information about how poorly such schedules can perform. The most general problem of maximizing maximum cost is shown to be reducible to n similar problems of scheduling n−1 jobs available at the same time. It is solved in O( mn+ n2) time, where m is the number of arcs in the precedence graph. When all release times are equal to zero, the problem of maximizing the total weighted completion time or the weighted number of late jobs is equivalent to its minimization counterpart with precedence constraints reversed with respect to the original ones. If there are no precedence constraints, the problem of maximizing arbitrary regular function reduces to n similar problems of scheduling n−1 jobs available at the same time.
ACCESSION #
18724134

 

Related Articles

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

  • A parametric characterization of local optimality. Dür, Mirjam // Mathematical Methods of Operations Research;2003, Vol. 57 Issue 1, p101 

    In a series of papers, Hiriart-Urruty proposed necessary and sufficient global optimality conditions for the so-called d.c. problem and the convex maximization problem. In this paper, we investigate the underlying local optimality conditions, which, in general, are necessary, but not sufficient...

  • A HEURISTIC ALGORITHM FOR THE n JOB, m MACHINE SEQUENCING PROBLEM. Campbell, Herbert G.; Dudek, Richard A.; Smith, Milton L. // Management Science;Jun70, Vol. 16 Issue 10, pB-630 

    This paper describes a simple algorithm for the solution of very large sequence problems without the use of a computer. It produces approximate solutions to the n job, m machine sequencing problem where no passing is considered and the criterion is minimum total elapsed time. Up to m-1 sequences...

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

  • HIERARCHICAL APPROACH TO STEEL PRODUCTION SCHEDULING UNDER A GLOBAL ENERGY CONSTRAINT. Boukas, E. K.; Haurie, A.; Soumis, F. // Annals of Operations Research;1990, Vol. 26 Issue 1-4, p289 

    This paper presents a model for the optimization of productivity in a steel plant comprised of four arc furnaces and three continuous casting machines and subject to a global limitation on the power supplied to the furnaces. The furnaces produce in batch mode and require a given amount of energy...

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

  • An Almost Optimal Heuristic for Preemptive Cmax Scheduling of Dependent Tasks on Parallel Identical Machines. Józefowska, Joanna; Mika, Marek; Różycki, Rafał; Waligóra, Grzegorz; Węglarz, Jan // Annals of Operations Research;Jul2004, Vol. 129 Issue 1-4, p205 

    We consider the problem of scheduling preemptable, dependent tasks on parallel, identical machines to minimize the makespan. The computational complexity of this problem remains open if the number of machines is fixed and larger than 2. The aim of this paper is to compare two heuristic...

  • AN INTERACTIVE MULTIPLE OBJECTIVE LINEAR PROGRAMMING METHOD FOR A CLASS OF UNDERLYING NONLINEAR UTILITY FUNCTIONS. Zionts, Stanley; Wallenius, Jyrki // Management Science;May83, Vol. 29 Issue 5, p519 

    This paper develops a method for interactive multiple objective linear programming assuming an unknown pseudo concave utility function satisfying certain general properties. The method is an extension of our earlier method published in this journal [18]. Various technical problems present in...

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