Browsing by Author "Pinedo, M"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops
    (1998) Singer, M; Pinedo, M
    We present and compare a number of branch and bound algorithms for minimizing the total weighted tardiness in job shops. There are basically two types of branching schemes. The first one inserts operations in a partial schedule, while the second one fixes arcs in the disjunctive graph formulation of the problem. The bounding schemes are based on the analysis of precedence constraints, and on the solution of nonpreemptive single machine subproblems that are subject to so-called delayed precedence constraints. We obtain optimal solutions for all the instances with ten jobs and ten machines that we consider, including three tardiness versions of a well-known 10 x 10 instance introduced by Muth and Thompson [1] in 1963.
  • Thumbnail Image
    Item
    A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop
    (WILEY, 1999) Pinedo, M; Singer, M
    We present a shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. The method decomposes the job shop into a number of single-machine subproblems that are solved one after another. Each machine is scheduled according to the solution of its corresponding subproblem. The order in which the single machine subproblems are solved has a significant impact on the quality of the overall solution and on the time required to obtain this solution. We therefore test a number of different orders for solving the subproblems. Computational results on 66 instances with ten jobs and ten machines show that our heuristic yields solutions that are close to optimal, and it clearly outperforms a well-known dispatching rule enhanced with backtracking mechanisms. (C) 1999 John Wiley & Sons, Inc.