Minimizing mean absolute deviation of completion times about a common due date

We consider a single machine scheduling problem in which the objective is to minimize the mean absolute deviation of job completion times about a common due date. We present an algorithm for determining multiple optimal schedules under restrictive assumptions about the due date, and an implicit enumeration procedure when the assumptions do not hold. We also establish the similarity of this problem to the two parallel machines mean flow time problem.     

Scheduling about a large common due date with tolerance to minimize mean absolute deviation of completion times

In this article the problem of minimizing the mean absolute deviation (MAD) of job completion times about an unrestricted given common due date with tolerance in the n-job, single-machine scheduling environment is considered. We describe some optimality conditions and show that the unrestricted version of the MAD problem with an arbitrary due date tolerance is polynomial by proposing a polynomial-time algorithm for identifying an optimal schedule. © 1994 John Wiley & Sons, Inc.     

Single-machine scheduling with early and tardy completion costs

We address a single-machine scheduling problem in which penalties are assigned for early and tardy completion of jobs. These penalties are common in industrial settings where early job completion can cause the cash commitment to resources in a time frame earlier than needed, giving rise to early completion penalties. Tardiness penalties arise from a variety of sources, such as loss of customer goodwill, opportunity costs of lost sales, and direct cash penalties. Accounting for earliness cost makes the performance measure nonregular, and this nonregularity has apparently discouraged researchers from seeking solutions to this problem. We found that it is not much more difficult to design an enumerative search for this problem than it would be if the performance measure were regular. We present and demonstrate an efficient timetabling procedure which can be embedded in an enumerative algorithm allowing the search to be conducted over the domain of job permutations.© 1993 John Wiley & Sons, Inc.     

Single- and multiple-processor models for minimizing completion time variance

This article concerns the scheduling of n jobs around a common due date, so as to minimize the average total earliness plus total lateness of the jobs. Optimality conditions for the problem are developed, based on its equivalence to an easy scheduling problem. It seems that this problem inherently has a huge number of optimal solutions and an algorithm is developed to find many of them. The model is extended to allow for the availability of multiple parallel processors and an efficient algorithm is developed for that problem. In this more general case also, the algorithm permits great flexibility in finding an optimal schedule.     

The single-machine absolute-deviation early-tardy problem with random completion times

We consider sequencing n jobs on a single machine subject to job completion times arising from either machine breakdowns or other causes. The objective is to minimize an expected weighted combination of due dates, completion times, earliness, and tardiness penalties. The determination of optimal distinct due dates or optimal common due dates for a given schedule is investigated. The scheduling problem for a fixed common due date is considered when random completion times arise from machine breakdowns. The optimality of a V-shaped about (a point) T sequence is established when the number of machine breakdowns follows either a Poisson or a geometric distribution and the duration of a breakdown has an exponential distribution. © 1996 John Wiley & Sons, Inc.     

Constant risk aversion in stochastic contests with exponential completion times

This article analyzes a class of stochastic contests among multiple players under risk‐averse exponential utility. In these contests, players compete over the completion of a task by simultaneously deciding on their investment, which determines how fast they complete the task. The completion time of the task for each player is assumed to be an exponentially distributed random variable with rate linear in the player's investment and the completion times of different players are assumed to be stochastically independent. The player that completes the task first earns a prize whereas the remaining players earn nothing. The article establishes a one‐to‐one correspondence between the Nash equilibrium of this contest with respect to risk‐averse exponential utilities and the nonnegative solution of a nonlinear equation. Using the properties of the latter, it proves the existence and the uniqueness of the Nash equilibrium, and provides an efficient method to compute it. It exploits the resulting representation of the equilibrium investments to determine the effects of risk aversion and the differences between the outcome of the Nash equilibrium and that of a centralized version.© 2016 Wiley Periodicals, Inc. Naval Research Logistics 66:4–14, 2019     

Minimizing total completion time in two-processor task systems with prespecified processor allocations

We consider the problem of scheduling multiprocessor tasks with prespecified processor allocations to minimize the total completion time. The complexity of both preemptive and nonpreemptive cases of the two-processor problem are studied. We show that the preemptive case is solvable in O(n log n) time. In the nonpreemptive case, we prove that the problem is NP-hard in the strong sense, which answers an open question mentioned in Hoogeveen, van de Velde, and Veltman (1994). An efficient heuristic is also developed for this case. The relative error of this heuristic is at most 100%. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 231–242, 1998     

Scheduling to minimize the weighted sum of completion times with secondary criteria

A result of Smith previously published in this journal [3], on the use of secondary criteria in scheduling problems, is shown to be incorrect and a counter example is presented. Heck and Roberts [2] suggested that their paper would be extended in the same way Smith's algorithm was. A new algorithm is given that converges to a local optimum for both problems.     

Minimizing the weighted sum of quadratic completion times on a single machine

This article discusses the scheduling problem of minimizing the weighted sum of quadratic completion times on a single machine. It establishes links between orderings of adjacent and nonadjacent jobs that lead to a powerful branch and bound method. Computational results show that this method clearly outperforms the state of the art algorithm. © 1995 John Wiley & Sons. Inc.     

On testing for decreasing mean residual life ordering

We consider the problem of testing for the decreasing mean residual life ordering introduced in Kochar and Wiens [14]. We treat both the one-sample and two-sample problems. The limiting distributions of the proposed test statistics are derived. © 1993 John Wiley & Sons, Inc.     

Probabilistic analysis of an asymptotically optimal solution for the completion time variance problem

Scheduling a set of n jobs on a single machine so as to minimize the completion time variance is a well‐known NP‐hard problem. In this paper, we propose a sequence, which can be constructed in O(n log n) time, as a solution for the problem. Our primary concern is to establish the asymptotical optimality of the sequence within the framework of probabilistic analysis. Our main result is that, when the processing times are randomly and independently drawn from the same uniform distribution, the sequence is asymptotically optimal in the sense that its relative error converges to zero in probability as n increases. Other theoretical results are also derived, including: (i) When the processing times follow a symmetric structure, the problem has 2^{⌊(n−1)/2⌋} optimal sequences, which include our proposed sequence and other heuristic sequences suggested in the literature; and (ii) when these 2^{⌊(n−1)/2⌋} sequences are used as approximate solutions for a general problem, our proposed sequence yields the best approximation (in an average sense) while another sequence, which is commonly believed to be a good approximation in the literature, is interestingly the worst. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 373–398, 1999     

Minimization of expected variance of completion times on single machine for stochastic jobs

This article deals with the problem of scheduling jobs with random processing times on single machine in order to minimize the expected variance of job completion times. Sufficient conditions for the existence of V-shaped optimal sequences are derived separately for general and ordered job processing times. It is shown that when coefficient of variation of random processing times are bounded by a certain value, an optimal sequence is V-shaped. © 1997 John Wiley & Sons, Inc.     

Minimizing the average deviation of job completion times about a common due date

This paper considers a single-machine scheduling problem in which penalities occur when a job is completed early or late. The objective is to minimize the total penalty subject to restrictive assumptions on the due dates and penalty functions for jobs. A procedure is presented for finding an optimal schedule.     

Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times

This paper deals with flowshop/sum of completion times scheduling problems, working under a “no-idle” or a “no-wait” constraint, the former prescribes for the machines to work continuously without idle intervals and the latter for the jobs to be processed continuously without waiting times between consecutive machines. Under either of the constraints the problem is unary NP-Complete for two machines. We prove some properties of the optimal schedule for n/2/F, no-idle/σC_i. For n/m/P, no-idle/σC_i, and n/m/P, no-wait/σC_i, with an increasing or decreasing series of dominating machines, we prove theorems that are the basis for polynomial bounded algorithms. All theorems are demonstrated numerically.     

Heuristics for minimizing mean tardiness for m parallel machines

The concept of parallel operations has been widely used in manufacturing and data processing. However, not many efficient methods have been proposed to reduce job tardiness. This article proposes an efficient heuristic to minimize the mean tardiness of a set of tasks with known processing times and due dates for single and m parallel machines. For the single-machine case, the proposed heuristic is compared with the well-known Wilkerson and Irwin algorithm; for the m parallel machine case, it is compared with an extension of the Wilkerson-Irwin algorithm. We also introduce a simple dispatching rule, and it is compared with some existing dispatching rules. The comprehensive simulation results show that the proposed heuristic performs better than the Wilkerson-Irwin algorithm at a significantly reduced computational time.     

Single-machine scheduling to minimize absolute deviation of completion times from a common due date

The article considers a single-machine n-job scheduling problem to minimize the sum of absolute lateness given a common due date. Two models are defined depending on whether the start time t₀ of schedules is arbitrary or fixed. Conditions are provided when those two models coincide. The developed branch-and-bound procedure is tested on nine known examples from the literature (6 ⩽ n ⩽ 14) and 90 medium-size random problems (15 ⩽ n ⩽ 25) with a fixed t₀.     

Online process mean estimation using L1 norm exponential smoothing

A basic assumption in process mean estimation is that all process data are clean. However, many sensor system measurements are often corrupted with outliers. Outliers are observations that do not follow the statistical distribution of the bulk of the data and consequently may lead to erroneous results with respect to statistical analysis and process control. Robust estimators of the current process mean are crucial to outlier detection, data cleaning, process monitoring, and other process features. This article proposes an outlier‐resistant mean estimator based on the L₁ norm exponential smoothing (L₁‐ES) method. The L₁‐ES statistic is essentially model‐free and demonstrably superior to existing estimators. It has the following advantages: (1) it captures process dynamics (e.g., autocorrelation), (2) it is resistant to outliers, and (3) it is easy to implement. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

基于平均互信息熵的复杂系统可靠性评定方法

可靠性评定是定量评估系统可靠性水平的重要途径,是对其可靠性进行定量控制的必要手段.某些复杂系统由于研制时间和经费的限制,现场试验样本量极其有限,依赖传统的基于大样本的数理统计方法将难以获得客观结论,因此其可靠性评定一直是工程实践中的技术难题.针对复杂系统可靠性评估和寿命预测时现场样本量不足的问题,提出了一种基于多源信息融合的可靠性评定方法.该方法利用平均互信息熵来度量多源验前信息对可靠性评定不确定性减少所起的作用,以此为依据确定多源信息融合权重,并通过融合验前分布进行复杂系统的可靠性评定,从而减少了评定过程中的主观性,增强了评定结论的可信性.最后通过仿真实例验证了方法的有效性.     

Large deviations of the winsorized mean of an exponential distribution

An asymptotic representation for large deviation probabilities of the Winsorized mean of a sequence of independent, identically distributed exponential random variables is derived. The Winsorized mean, a linear combination of exponential order statistics, is first transformed into a weighted sum of exponential random variables, and then a large deviation theorem for weighted sums can be applied. The representation obtained is then compared with results already known for the mean and the median, the two extreme cases of the Winsorized mean.     

A mean cost approximation for transportation problems with stochastic demand

Among the many tools of the operations researcher is the transportation algorithm which has been used to solve a variety of problems ranging from shipping plans to plant location. An important variation of the basic transportation problem is the transportation problem with stochastic demand or stochastic supply. This paper presents a simple approximation technique which may be used as a starting solution for algorithms that determine exact solutions. The paper indicates that the approximation technique offered here is superior to a starting solution obtained by substituting expected demand for the random variables.