The author states that, in the original paper (D.L. Hoitomt and P.B. Luh ibid., vol. 9, no. 1, p. 1-13, 1993), the model formulation of the scheduling problem is highly irregular. If one were to consider the formulation by itself it would seem that since neither the precedence nor processing time constraints are linked to time, we could set all /spl delta//sub ijkh/=0 and obtain a feasible solution with jobs overlapping on machines. It is noted that in the subsequent relaxation of the capacity constraint, the binary variables have been set to 1 from start to finish time of the corresponding operation to account for capacity. The need for the model formulation to include such constraints explicitly is discussed, and the original authors discuss the relevance of the comments. The existence of related and similar results in previous works is also considered.>

The use of Lagrangian relaxation to schedule job shops, which include multiple machine types, generic precedence constraints, and simple routing considerations, is explored. Using an augmented Lagrangian formulation, the scheduling problem is decomposed into operation-level subproblems for the selection of operation beginning times and machine types, with given multipliers and penalty coefficients. The multipliers and penalty coefficients are then updated at the higher level. The solution forms the basis of a list-scheduling algorithm that generates a feasible schedule. A procedure is also developed to evaluate the quality of this feasible schedule by generating a lower bound on the optimal cost. Numerical examples are taken from a representative industrial job shop. High-quality schedules are efficiently generated every other day over a three-week period, with costs generally within 4% of their respective lower bounds. The methodology compares favorably with knowledge-based scheduling.>

A method for batching jobs within a class in advance of sequencing is presented. It is shown that under certain simplifying assumptions, optimal batch composition can be obtained independent of the sequencing problem. This composition is determined by assigning parts to batches according to an earliest due date (EDD) rule. An efficient methodology for sequencing the batches based on the Lagrangian relaxation technique is presented. The solution to the Lagrangian relaxation dual problem is a lower bound on the cost of the optimal schedule. If the assumptions are relaxed, the EDD rule becomes a heuristic for solving the batch composition problem, and the same batch sequencing algorithm can be used to obtain a schedule. In that case, the dual cost is a lower bound on the cost of all possible sequences with the same batch composition. Preliminary results show that good schedules can be efficiently obtained.>

A distributed job shop scheduling algorithm has been implemented in the LAN (local area network) environment. The algorithm is a good candidate for distributed implementation since much of the computation time required for a solution is expended in distributable portions of the algorithm. A distributed processing support system (DPSS) was developed to ease the implementation of this and future distributed algorithms. Preliminary results indicate considerable potential for reducing the computation time. Additional portions of the algorithm may be distributed to improve the results, and streamlining of the underlying communication mechanism of DPSS is underway.>

An exploration is made of the use of Lagrangian relaxation to schedule job shops, which include multiple machine types, generic precedence constraint, and simple routing considerations. From an augmented Lagrangian formulation, a decomposed solution methodology is developed using a Jacobi-type iterative approach. The subgradient method and the multiplier method are used to update the multipliers and the penalty coefficients. The dual solution forms the basis of a list scheduling algorithm which generates a feasible schedule. Unfortunately, the dual cost is not a lower bound on the optimal cost because of the Jacobi iterative technique employed. In order to evaluate the schedule, a second problem formulation is adopted. Its solution would ordinarily require prohibitive memory and considerable computation time. By utilizing part of the multipliers obtained from the first problem formulation, however, an effective lower bound on the optimal cost can be quickly obtained. A numerical example is given in which schedule cost is within 2% of its lower bound.>

A methodology for scheduling independent jobs with due dates on identical, parallel machines is presented. The jobs have different levels of importance and various processing times on the machines, and the objective is to minimize the total weighted job tardiness of the schedule. Since the problem is NP hard, the goal is not to obtain the optimal schedule. Rather, an efficient near-optimal algorithm based on Lagrangian relaxation is presented. This approach provides a lower bound on the cost, which can be used as a measure of suboptimality. According to an implementation for a work center at Pratt and Whitney, most schedules generated are within 1% of the optima with reasonable CPU times. Furthermore, the method provides valuable job interaction information, which shop floor management uses to answer 'what if' questions, to reconfigure the schedule to accommodate dynamic changes, and to schedule new jobs.>

The authors present a methodology for scheduling independent jobs with due dates on identical parallel machines. The jobs have different levels of importance and various processing times on the machines, and the objective is to minimize the total weighted job tardiness of the schedule. Since the problem is NP-hard, the goal is not to obtain the optimal schedule. Rather, an efficient near-optimal algorithm based on Lagrangian relaxation is presented. A nice feature of this approach is that it provides a lower bound on the cost, which can be used as a measure of suboptimality. On most problems tested, results are within 1% of the optima and have reasonable CPU times. Furthermore, the method provides job interaction information, which is then used to provide quick answers to 'what if' questions, to reconfigure the schedule to accommodate dynamic changes, and also to schedule jobs.>

A manufacturing system with one server (machine), two classes of jobs, finite buffer sizes and nonnegligible setup times is analyzed. Classes are served in a fixed order. A new cycling service discipline called "triggered" cycling is introduced as a type of exhaustive cycling where a job must be present to process before the setup for that class takes place. The state of the machine, whether in setup or in processing, is explicitly considered in the model. Utilization, mean queue length and cycle time are derived by using Markovian analysis, first under a fixed lot size environment and then with random lot sizes. With lot sizes fixed (deterministic), increasing arrival rates, setup times and service times generally increase utilization, cycle time and queue length. Sensitivity analyses indicate a minimum exists for queue length with respect to lot size. When lot sizes are random, negligible variations in cycle time result, with somewhat smaller queue length as compared to the fixed lot size case. Despite lack of a product form solution to the problem, an approximate mean value analysis yielding cycle time is developed and the results are compared to Markovian analysis. Numerical studies show robustness of the mean value analysis for utilizations under 0.7.