We treat a virtual job-shop problem of sequencing n jobs on m unique machines. Each machine is outsourced with known renting cost per time unit. The job-operation processing times have random durations, and each job has its tardiness penalty function. The objective is to determine in advance the machine booking schedule that maximizes an economic gain. We present a simulation based on a cyclic coordinate descent search- algorithm and greedy priority dispatching rule that delivers a rent timetable that minimizes the expected total cost.
Management often fails in adjusting the organizational facility availabilities with the delivery commitments to clients. On one hand, the occurrence of ‘over-commitment’, i.e., accepting too many orders in relation to existing facilities is problematic (Engwall and Jerbrant, 2003), but on the other hand, facility redundancy is cost prohibitive. A predictive schedule serves very important functions in adjusting facilities to commitments or vice versa (Mehta and Uzsoy, 1998). An essential element in preparing the predictive schedule is to guarantee facility availabilities within the planning horizon (Bowers, 1995).
A pre-schedule can outperform on-line dispatching heuristic rules in shop environments where stochastic durations are assigned to the operation but uncertainty does not exceed a certain threshold (Aytug et al., 2005). Byeon et al. (1998) and Wu et al. (1999) proposed an elegant way to tradeoff between static and dynamic scheduling, showing how to make some important scheduling decisions before schedule execution and relegate the remainder of the scheduling choices to future points in time. Small fluctuations on the shop-floor are dealt with dynamically but initial decisions impose structure in the shop.
The common schedule restrictions are: (1) activity precedence feasibilities (i.e., all their respective-immediate preceding activities have been completed), (2) facility availabilities, and (3) delivery commitments (due dates). The goal, which is more akin to deterministic scheduling, is to make scheduling and facilities allocation decisions subject to these restrictions that will decrease (optimize) the entire expenses dependent on schedule decisions. Since stochastic durations are assigned to each job-operation, the ‘optimized’ predictive schedule should function as a baseline for executing the orders rather than an exact prediction of their execution. The predictive scheduling is the baseline for revising plans and schedules (if warranted) following corrective actions, and should also protect the delivery commitments from any sources of uncertainty that may occur (Herroelen and Leus, 2005). A planning–monitoring–controlling cycle should be implemented continuously in process until the projects are completed (Meredith and Mantel, 2000).
The problem is to prepare in advance a facility deliveries timetable for a job shop that satisfies a predictive schedule to optimize an economic gain. Some studies on sequencing activities with random durations on a single machine with this objective have been published until now. Trietsch (1993) described a problem where a hub airport acts like a single machine. Incoming flights from many origins feed outgoing flights to equally many destinations. If an incoming flight is late, outgoing flights that are fed by it may also be delayed. Alternatively, aircraft may leave before some feeding flights arrive, thereby incurring high misconnection penalties. By optimizing the scheduled ground time of each plane, one can minimize the expected sum of waiting costs and tardiness penalties. The author stated that the problem is non-linear and highly combinatorial, so for a life-size problem it is not practical to solve it to optimality. Therefore, an important part of his paper was devoted to heuristic solutions using blocks for scheduling and adjacent pairwise interchanges for sequencing. Soroush and Fredendall (1994) studied the static single machine scheduling problem with earliness and tardiness costs where job processing times are random variables and due dates are distinct and deterministic. The objective was to identify an optimal sequence which minimizes the total expected earliness plus tardiness cost. Soroush (1999) studied the problem of simultaneous due-date determination and sequencing of a set of n jobs on a single machine where processing times are random variables and job earliness and tardiness costs are distinct. His objective was to determine the optimal sequence and the optimal due dates which jointly minimize the expected total earliness and tardiness cost. Elmaghraby et al. (2000) treated the problem of sequencing several activities with random durations on a single facility with the objective of determining their start times to maximize an economic gain, subject to restrictions on their availabilities.
Our paper extends these works, expanding the problem to a model with several machines. The solution of this problem is generated by a cyclic coordinate descent search algorithm seeking minimum total cost. A special dispatching rule is implemented in the scheduling simulation in order to simultaneously satisfy the scheduling restrictions and minimize (optimize) the job shop's expenses.
There has been a large body of research into the design of scheduling rules and heuristics for various classes of scheduling problems (Morton and Pentico 1993). The design of effective heuristic procedures for generating high quality solutions to practical problems can be a very helpful tool. Although such heuristics can be effective in specific circumstances, they are not perfect and their myopic nature can often lead to sub-optimal decisions. Most real scheduling systems are either based on dispatch rules, or at least use them to some degree. The books by Pinedo (1995) and Pinedo and Chao (1999) contain sections devoted to dispatching procedures, and also present examples of real scheduling systems that use dispatch rules. One explicit characteristic of the conventional scheduling problem is that they address a single criterion. However, multi-objective scheduling models are required for the real-life scheduling problem. Chann et al. (2002) considered the multi-objective flow-shop scheduling problem by considering makespan, total flowtime, total tardiness, and maximum tardiness. They proposed the gradual-priority weighting approach to search the Pareto optimal solutions for the multi-objective flow-shop scheduling problem. Varadharajan and Rajendran (2005) considered the problem of permutation flow-shop scheduling with the objectives of minimizing the makespan and total flowtime of jobs, and presented a multi-objective simulated-annealing algorithm. As they stated, the problem of scheduling in permutation flow-shops has been extensively investigated by many researchers. Exact and heuristic algorithms, where efficient solutions with respect to time and cost-based objectives are generated, had been proposed over the years for solving static permutation flow-shop scheduling problems (e.g., Slowinski, 1981; Daniels, 1989; Dean et al., 1992; Speranza and Vercellis, 1993).
