...must perform at globally satisfactory level for efficient usage of resources even under these changes, and second, the system must allow sufficient flexibility for changes and adjustments.

To achieve the first goal of high quality global performance, a well-planned a priori schedule is usually required. A static scheduling method is typically used to create a fine-tuned, potentially optimal schedule at the beginning of the planning horizon. The static approach typically generates a detailed schedule assuming perfect information about the system's current and future states. In reality, disturbances and changes in the system could render this static schedule difficult, if not impossible, to follow. When updates are made to accommodate the system disturbances, the overall scheduling performance is likely to deteriorate. Thus, a schedule "optimized" with respect to what is known at the planning time may perform poorly under these changing conditions.

To achieve the second goal of flexibility, dynamic dispatching policies are typically used, where scheduling decisions are made throughout the course of production. This dynamic scheduling approach usually utilizes myopic priority indices and greedy heuristics, which may lead to poor global performance. However, its inherent flexibility and ability to utilize up-to-date potentially state-dependent information makes dynamic scheduling a practical tool in uncertain environments. For example, Lawrence and Sewell (1997) show empirically that the performance of "optimized" static schedules may deteriorate rapidly with the processing time uncertainty, and that simple dynamic dispatching heuristics may provide a far superior performance. Another similar study by Kutanoglu and Sabuncuoglu (2001) reports similar observations when considering uncertainties in job processing times and machine availability.

In this paper, we propose to address scheduling robustness by a method that reconciles the benefits of static and dynamic scheduling. We shift the focus of a priori scheduling to identifying decisions that are critical to global performance under the presence of random changes and disturbances. We find and optimize these critical decisions using a priori stochastic information and Lagrangian relaxation, which partially solves the scheduling problem. We call this stage preprocessing, which is followed by the so-called dynamic adaptation stage, where the unsolved scheduling decisions unfold over time using a dynamic scheduling approach.

Treating scheduling problems in uncertain environments did not attract much attention in the literature until the early 1980s. One approach is to reschedule all the jobs from scratch every time an uncertain event occurs (Muhlemann et al., 1982; Yamamoto and Nof, 1985; Church and Uzsoy, 1992; Wu et al., 1992, 1993; Baptiste and Favrel, 1993). Researchers have also proposed schedule repair methods that compute a temporary schedule after each machine breakdown that attempt to bring the system back to schedule in a finite amount of time. The "match-up scheduling" method proposed by Gallego (1988a, 1988b) and Bean et al. (1991) belongs to this category. A similar schedule update heuristic that uses the second-moment information for uncertain processing times is proposed by Maddox and Birge (1992).

Instead of repairing a prespecified schedule, Mehta and Uzsoy (1997) propose a method that inserts idle times into the schedule in anticipation of schedule disruptions. Another approach is to split the scheduling activity into planning and dispatching stages. The planning stage computes the pricing or resource usage costs using global information, while the dispatching phase makes use of the resource pricing and up-to-date shop conditions, and deals with uncertainties. This approach is both general and effective as demonstrated by Morton et al. (1986, 1988) and Roundy et al. (1991). A similar approach by Wu et al. (1999) partitions the operations of all jobs into an ordered sequence of subsets in the planning phase. This identifies and resolves the supposedly critical scheduling decisions through a graph-theoretic preprocessing. The second stage completes the schedule dynamically using a dispatching heuristic.

The approach described in this paper is parallel to the two-stage methods in the last group of papers, as we first preprocess the problem via stochastic analysis to create a partial ranking of jobs first, and then adapt these decisions and make the remaining scheduling decisions as the real events unfold in real-time. This paper focuses on the issue of scheduling robustness. For the purposes of this study, we define "robustness" from the viewpoint of a scheduling procedure. A procedure or an algorithm is said to be more robust than an alternative if the schedules it generates achieve better performance (as defined by the objective function) under the same set of random disturbances and changes. For other related definitions of robustness, we refer the reader to Leon et al. (1994) and Kouvelis and Yu (1996).

2. The proposed scheduling scheme

We propose a two-stage approach to achieve scheduling robustness: (i) preprocessing: based on the knowledge of the problem instance and data uncertainty, resolve a subset of sequencing decisions critical for the overall scheduling performance; and (ii) dynamic adaptation: complete actual scheduling (timing and sequence) using the most current data when uncertainties unfold in real-time. We use the job shop scheduling problem to present and test the methodology.

In the preprocessing stage, we use an Integer Programming (IP) formulation of the Job shop Scheduling Problem (JSP). Instead of using the IP model to generate a detailed static schedule, we use it to analyze the criticality of scheduling decisions. First, we decompose the JSP to job-level subproblems using the Lagrangian relaxation of the machine capacity constraints. This results in job-level subproblems, each with a special network structure, which can be solved efficiently. Second, we reformulate each job-level subproblem to include chance constraints that capture processing time uncertainty, while keeping the special network structure intact. Although capacity-infeasible as a whole, the solution of the relaxed problem (the combination of job-level schedules) produces a lower bound for the corresponding (chance-constrained) JSP. Next, we iteratively improve the Lagrangian lower bound using a subgradient optimization search algorithm. Although capacity-infeasible, the lower bound solution has useful information regarding the overall criticality of jobs. Therefore, in each subgradient iteration, we also compute the so-called Lagrangian ranking among the jobs based on their position in the lower bound schedule. The estimated performance of each Lagrangian ranking is captured with a feasibility restoration heuristic. When the subgradient search algorithm stops, we report the Lagrangian ranking that produces the best estimated performance. Finally, we preprocess the scheduling instance by prioritizing the jobs according to their Lagrangian ranking, i.e., a subset of operations are sequenced based on their criticality captured in the best reported Lagrangian ranking.

In the dynamic adaptation stage, the preprocessed schedule is used as an input to be followed in real time, while the remaining prioritization of jobs is done dynamically over time during which processing times can vary. Hence, the preprocessed schedule is implemented and the remaining schedule is generated using the actual (realized) processing times. The above scheme can be viewed as a variation of the Preprocess-First-Schedule-Later (PFSL) scheme proposed by Wu et al. (1999). Wu et al. (1999) used a branch-and-bound algorithm for the a priori analysis and a dynamic dispatching rule for detailed scheduling.

3. The robust scheduling methodology

In this section, we formalize the proposed scheduling scheme by first introducing the classical JSP model (in Section 3.1) we use for the analysis. We then describe the Lagrangian relaxation of JSP (Section 3.2), and introduce the chance constraints which capture the processing time uncertainty (Section 3.3). We provide a description of a scaling scheme used to reduce computational burden and define the Lagrangian ranking (Section 3.5), and detail a specialized version of the subgradient search algorithm (Section 3.6). We end the section by an outline of the overall scheduling scheme with the added technical details.

3.1. The job shop scheduling model

We consider the classical JSP where a set of jobs is to be completed on multiple machines. Each job consists of a series of operations that represent the production steps of the job. Due to processing requirements, the operations of a job are subject to (serial, or as sometimes called, linear) precedence constraints. Each production step (operation) requires a specific machine and once the processing of an operation starts it cannot be preempted by any other operation. The collection of operation processing times and their corresponding machine requirements represent the job routing. Each machine can only process one operation at a time. This requirement defines the machine capacity constraints. Each job has a due date and a weight, and the objective is to find a schedule which minimizes the total weighted tardiness.

Although there are alternative ways to formulate the problem (see Pinedo (2001) for additional discussion), we state the time-indexed IP formulation of the JSP due to Pritsker et al. (1969). In this formulation the decision variables ([X.sub.ijt]) are defined as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

The JSP can be formulated as follows (we set the variables with out-of-range indices to zero):

(JSP)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (2)

subject to

[X.sub.i,j,t+1] [greater than or equal to] [X.sub.i,j,t], [for all]i, j, t < T, (3)

[X.sub.i,j,t+1] [less than or equal to] [X.sub.i,j-1,t-[p.sub.i,j-1]], [for all]i, j > 1, t, (4)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

[X.sub.i,j,t] [member of] {0, 1}, [for all]i, j, t. (6)

The first set of constraints (3) makes sure that once an operation is started,...

NOTE: All illustrations and photos have been removed from this article.



More articles from IIE Transactions
A Benders-based heuristic for the robust capacitated international sou..., November 01, 2004
Accounting for input-model and input-parameter uncertainties in simula..., November 01, 2004
Management for Quality in High-Technology Enterprises.(Book Review), November 01, 2004

Looking for additional articles?
Search our database of over 3 million articles.

Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication name or publication date.

About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.

Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information.