Minimizing total completion time subject to release dates and sequence-dependent processing times

Bianco, Lucio; Dell'Olmo, Paolo; Giordani, Stefano
March 1999
Annals of Operations Research;1999, Vol. 86 Issue 1-4, p393
Academic Journal
We consider the problem of scheduling jobs with release dates and sequence-dependent processing times on a single machine to minimize the total completion time. We show that this problem is equivalent to the Cumulative Traveling Salesman Problem with additional time constraints. For this latter problem, we give a dynamic programming formulation from which lower bounds are derived. Two heuristic algorithms are proposed. Performance analysis of both lower bounds and heuristics on randomly generated test problems are carried out. Moreover, the application of the model and algorithms to the real problem of sequencing landing aircraft in the terminal area of a congested airport is analyzed. Computational results on realistic data sets show that heuristic solutions can be effective in practical contexts.


Related Articles

  • INTEGER PROGRAMMING POST-OPTIMAL ANALYSIS WITH CUTTING PLANES. Klein, Dieter; Holm, Søren // Management Science;Jan1979, Vol. 25 Issue 1, p64 

    Sufficient conditions have been developed for testing the optimality of solutions to all-integer and mixed-integer linear programming problems after coefficient changes in the right hand side and the objective function, or after introduction of new variables. The same conditions can be used as...

  • A multicriteria approach for optimizing bus schedules and school starting times. Fügenshuh, Armin; Martin, Alexander // Annals of Operations Research;Oct2006, Vol. 147 Issue 1, p199 

    In many rural counties pupils on their way to school are a large, if not the largest group of customers for public mass transit. Hence an effective optimization of public mass transit in these regions must include the traffic caused by pupils. Besides a change in the schedules of the buses and...

  • ON THE MINIMIZATION OF COMPLETION TIME VARIANCE WITH A BICRITERIA EXTENSION. Ghosh, Jay B.; Wells, Charles E. // Operations Research;Nov/Dec92, Vol. 40 Issue 6, p1148 

    We discuss a single-machine scheduling problem where the objective is to minimize the variance of job completion times. To date, the problem has not been solved in polynomial time. This paper presents a dynamic programming algorithm that is pseudopolynomial in complexity. We also propose a fully...

  • EXTREME POINT MATHEMATICAL PROGRAMMING. Kirby, M. J. L.; Love, H. R.; Swarup, Kanti // Management Science;May72, Vol. 18 Issue 9, p540 

    The paper considers a class of optimization problems. The problems are linear programming problems: maximize ex subject to Ax = b with the additional constraint that x must also be an extreme point of a second convex polyhedron Dx = d. X ≥ 0. A cutting-plane algorithm for solving such...

  • Local Convergence of an Inexact-Restoration Method and Numerical Experiments. Birgin, E. G.; Martínez, J. M. // Journal of Optimization Theory & Applications;Nov2005, Vol. 127 Issue 2, p229 

    Local convergence of an inexact-restoration method for nonlinear programming is proved. Numerical experiments are performed with the objective of evaluating the behavior of the purely local method against a globally convergent nonlinear programming algorithm.

  • BRANCH-AND-BOUND METHODS: A SURVEY. Lawler, E. L.; Wood, D. E. // Operations Research;Jul/Aug66, Vol. 14 Issue 4, p699 

    The essential features of the branch-and-bound approach to constrained optimization are described, and several specific applications are reviewed. These include integer linear programming (LAND-DOIG and BALAS methods), nonlinear programming (minimization of nonconvex objective functions), the...

  • OFF-DAY SCHEDULING WITH HIERARCHICAL WORKER CATEGORIES. Emmons, Hamilton; Burns, Richard N. // Operations Research;May/Jun91, Vol. 39 Issue 3, p484 

    A work force includes workers of m types The worker categories are ordered, with type-1 workers the most highly qualified, type-2 the next, and so on. If the need arises, a type-k worker is able to substitute for a worker of any type j> k (k = 1,..., m-1). For 7-day-a-week operation, daily...

  • COMPUTATIONAL EXPERIENCE WITH A 'BALASIAN' INTEGER PROGRAMMING ALGORITHM. Freeman, Reoul J. // Operations Research;Sep/Oct66, Vol. 14 Issue 5, p935 

    A recent and significant addition to the literature of partial enumeration methods for solving integer linear programming problems has been the work of Balas. This paper describes some computational experience with a version of the algorithm and discusses future avenues of research that may be...

  • A LINEAR PROGRAMMING SOLUTION TO THE GENERAL SEQUENCING PROBLEM. von Lanzenauer, Christoph Haehling; Himest, Richard C. // CORS Journal;Jul70, Vol. 8 Issue 2, p129 

    This paper presents, for the general sequencing problem, an integer linear programming formulation with a special structure. The basic feature of the model, which differs from previous integer programming formulations, is that the coefficients in the constraints are zeros and ones only. The...


Read the Article


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

Try another library?
Sign out of this library

Other Topics