Sequencing n jobs on two machines with setup,processing and removal times separated

The paper extends the machine flow-shop scheduling problem by separating processing time into setup, processing and removal times.     

Applications of renewal theory in analysis of the free-replacement warranty

Under a free-replacement warranty of duration W, the customer is provided, for an initial cost of C, as many replacement items as needed to provide service for a period W. Payments of C are not made at fixed intervals of length W, but in random cycles of length Y = W + γ(W), where γ(W) is the (random) remaining life-time of the item in service W time units after the beginning of a cycle. The expected number of payments over the life cycle, L, of the item is given by M_Y(L), the renewal function for the random variable Y. We investigate this renewal function analytically and numerically and compare the latter with known asymptotic results. The distribution of Y, and hence the renewal function, depends on the underlying failure distribution of the items. Several choices for this distribution, including the exponential, uniform, gamma and Weibull, are considered.     

Shock models with phase type survival and shock resistance

New closure theorems for shock models in reliability theory are presented. If the number of shocks to failure and the times between the arrivals of shocks have probability distributions of phase type, then so has the time to failure. PH-distributions are highly versatile and may be used to model many qualitative features of practical interest. They are also well-suited for algorithmic implementation. The computational aspects of our results are discussed in some detail.     

M/M/1 queues with interdependent arrival and service processes

We study via simulation an M/M/1 queueing system with the assumption that a customer's service time and the interarrival interval separating his arrival from that of his predecessor are correlated random variables having a bivariate exponential distribution. We show that positive correlation reduces the mean and variance of the total waiting time and that negative correlation has the opposite effect. By using spectral analysis and a nonparametric test applied to the sample power spectra associated with certain simulated waiting times we show the effect to be statistically significant.     

Flowshop sequencing problem with ordered processing time matrices: A general case

The ordered matrix flow shop problem with no passing of jobs is considered. In an earlier paper, the authors have considered a special case of the problem and have proposed a simple and efficient algorithm that finds a sequence with minimum makespan for a special problem. This paper considers a more general case. This technique is shown to be considerably more efficient than are existing methods for the conventional flow shop problems.     

Scheduling workers in a constricted area

A generalization of the equi-partitioning problem, termed the 2D-Partition Problem, is formulated. The motivation is an aircraft maintenance scheduling problem with the following characteristics. The complete maintenance overhaul of a single aircraft requires the completion of some 350 tasks. These tasks require a varying number of technicians working at the same time. For large subsets of these 350 tasks, the constraining resource is physical space—tasks must be completed in a physical space of limited size such as the cockpit. Furthermore, there is no precedence relationship among the tasks. For each subset, the problem is to schedule the tasks to minimize makespan. Let m denote the maximum number of technicians that can work at the same time in the physical area under consideration. We present optimization algorithms for m = 2 and 3. © 1996 John Wiley & Sons, Inc.     

An evaluation of scheduling heuristics for dynamic single-processor scheduling with early/tardy costs

In an endeavor to broaden the application of scheduling models to decisions involving the use of a manager's time we use simulation to investigate the performance of a number of simple algorithms (including eight priority rules and a construction heuristic) in a dynamic setting with tasks arriving (randomly) and scheduling decisions being made, over time. We compare these simple methods relative to a bound that uses an adjacent pairwise interchange algorithm. We model uncertainty in task durations, and costs being incurred for early and tardy task completion (representative of JIT settings). In addition to evaluating the efficacy of the scheduling rules and various preemption strategies (using ANOVA), we highlight the managerial implications of the effects of eight environmental parameters. © 1996 John Wiley & Sons, Inc.     

A new polynomial algorithm for maximum value flow with an efficient parallel implementation

A new algorithm is presented for finding maximal and maximum value flows in directed single-commodity networks. Commonly algorithms developed for this problem find a maximal flow by gradually augmenting (increasing) a feasible flow to a maximal flow. In the presented algorithm, at the beginning of each step or iteration, the flow on arcs is assigned to flow capacity. This may lead to an infeasible flow violating flow conservation at some nodes. During two passes of a MAIN step, consisting of a forward pass and a backward pass, the flow is reduced on some arcs to regain feasibility. The network is then pruned by omitting saturated arcs, and the process is repeated. The parallel implementation of the algorithm applies the two main steps at the same time to the same network. The outputs of the two steps are compared and the processing continues with the higher feasible flow. The algorithm is simple, intuitive, and efficient. © 1993 John Wiley & Sons, Inc.     

On estimating survival for reliability models based on age-related stochastic comparisons

A new class of nonparametric reliability models is introduced and studied. A distribution is said to be better at age s than at age t (sBt) if the residual lifetime at age s is stochastically greater than or equal to the residual lifetime at age t. Applications to various forms of replacement policies, including the cannibalization of failed systems, are noted. For fixed s < t, the problem of estimating a survival curve assumed to belong to the sBt class is addressed using recursive methods. An sBt estimator is derived in closed form, and its uniform strong consistency at an optimal rate of convergence is demonstrated. A simulation study strongly supports the claim that the sBt estimator tends to outperform the empirical survivor function in small- and moderate-size samples. © 1993 John Wiley & Sons, Inc.