TITLE

Single-machine scheduling to minimize maximum tardiness with minimum number of tardy jobs

AUTHOR(S)
Gupta, J. N. D.; Hariri, A. M. A.; Potts, C. N.
PUB. DATE
December 1999
SOURCE
Annals of Operations Research;1999, Vol. 92 Issue 1-4, p107
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
This paper develops a branch and bound algorithm for solving the single-machine scheduling problem with the objective of minimizing the maximum tardiness of any job, subject to the constraint that the total number of tardy jobs is minimum. The algorithm uses a new lower bounding scheme, which is based on due date relaxation. Various dominance rules are used in the algorithm to limit the size of the search tree. Results of extensive computational tests show that the proposed branch and bound algorithm is effective in solving problems with up to 1000 jobs.
ACCESSION #
18668529

 

Related Articles

  • APPLICATION OF THE BRANCH AND BOUND TECHNIQUE TO SOME FLOW-SHOP SCHEDULING PROBLEMS. Ignall, Edward; Schrage, Linus // Operations Research;May/Jun65, Vol. 13 Issue 3, p400 

    The branch-and-bound technique of LITTLE, ET AL. and LAND AND DOIG is presented and then applied to two flow-shop scheduling problems. Computational results for up to 9 jobs are given for the 2-machine problem when the objective is minimizing the mean completion time. This problem was previously...

  • Algorithms for the single machine total weighted completion time scheduling problem with release times and sequence-dependent setups. Fuh-Der Chou; Hui-Mei Wang; Tzu-Yun Chang // International Journal of Advanced Manufacturing Technology;Nov2009, Vol. 43 Issue 7/8, p810 

    This paper considers the problem of scheduling n jobs on a single machine to minimize the total weighted completion time in the presence of sequence-dependent setup times and release times. To the best of our knowledge, little research has been devoted to this scheduling problem. Therefore, we...

  • A BRANCH-BOUND SOLUTION TO THE GENERAL SCHEDULING PROBLEM. Greenberg, Harold H. // Operations Research;Mar/Apr68, Vol. 16 Issue 2, p353 

    A mixed integer formulation is presented for the general n job, m machine scheduling problem. This formulation is shown to reduce to a series of noninteger L.P. problems of moderate proportions when applying the branch-bound technique. Solutions are presented for the two problems: minimize...

  • An Improvement on Branch and Bound in Flowshop Scheduling: Probabilistic Processing Time Case. Pararach, S.; Sukcharoenpong, P.; Charnsethikul, P. // International MultiConference of Engineers & Computer Scientists;2006, p784 

    The scheduling is classified as an NP-completed problem challenged for many researchers. This paper concerns with a flowshop scheduling problem with uncertain processing time. The model consists of a set of machines (multiple machines) and a set of jobs in a flowshop plant. The uncertain...

  • A New Method of Scheduling UET Tasks on Parallel Machines. Zinder, Yakov; Singh, Gaurav; Weiskircher, Rene // International MultiConference of Engineers & Computer Scientists;2006, p796 

    The paper describes a new method of scheduling partially ordered unit execution time tasks on parallel machines. The goal is to minimize the largest completion time. It is well known that this scheduling problem is NP-hard in the strong sense, and the commonly used approach, guaranteeing the...

  • Optimal Scheduling of Cooperative Tasks in a Distributed System Using an Enumerative Method. Peng, Dar-Tzen; Shin, Kang O. // IEEE Transactions on Software Engineering;Mar93, Vol. 19 Issue 3, p253 

    This paper considers preemptive (resume) scheduling of cooperative tasks that have been preassigned to a set of processing nodes in a distributed system, where each task is assumed to consist of several modules. During the course of their execution, these tasks communicate with each other to...

  • A GRAPH-THEORETIC DECOMPOSITION OF THE JOB SHOP SCHEDULING PROBLEM TO ACHIEVE SCHEDULING ROBUSTNESS. Wu, S. David; Byeon, Eui-Seok; Storer, Robert H. // Operations Research;Jan/Feb99, Vol. 47 Issue 1, p113 

    In this paper we study the weighted tardiness job-shop scheduling problem, taking into consideration the presence of random shop disturbances. A basic thesis of the paper is that global scheduling performance is determined primarily by a subset of the scheduling decisions to be made. By making...

  • A branch-and-bound procedure for the generalized resource-constrained project scheduling problem. Demeulemeester, Erik L.; Herroelen, Willy S. // Operations Research;Mar/Apr97, Vol. 45 Issue 2, p201 

    In this paper a branch-and-bound procedure is described for scheduling project activities subject to precedence diagramming type of precedence relations, ready times, due dates, and variable multiple resource availability constraints, where the objective is to minimize project duration. The...

  • ON THE N-JOB, ONE-MACHINE, SEQUENCE-INDEPENDENT SCHEDULING PROBLEM WITH TARDINESS PENALTIES: A BRANCH-BOUND SOLUTION. Shwimer, Joel // Management Science;Feb1972, Vol. 18 Issue 6, pB-301 

    An efficient branch-bound algorithm is presented for solving the n-job, sequence-independent, single machine scheduling problem where the goal is to minimize the total penalty costs resulting from tardiness of jobs. The algorithm and computational results are given for the case of linear penalty...

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