On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation

We study the scheduling situation in which a set of jobs subjected to release dates and deadlines are to be performed on a single machine. The objective is to minimize a piecewise linear objective function ∑_jF_j where F_j(C_j) corresponds to the cost of the completion of job j at time C_j. This class of function is very large and thus interesting both from a theoretical and practical point of view: It can be used to model total (weighted) completion time, total (weighted) tardiness, earliness and tardiness, etc. We introduce a new Mixed Integer Program (MIP) based on time interval decomposition. Our MIP is closely related to the well‐known time‐indexed MIP formulation but uses much less variables and constraints. Experiments on academic benchmarks as well as on real‐life industrial problems show that our generic MIP formulation is efficient. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Multiechelon repairable-item provisioning in a time-varying environment using the randomization technique

Multiechelon repairable-item provisioning systems are considered under a time-varying environment. Such conditions could arise, for example, in a military context where a shift from peacetime operation to wartime operation takes place; or, in a civilian setting where a public transit system decides to increase its hours of operation or frequency of service. Exact Markovian models, incorporating a finite population of repairable components and limited repair capacity (nonample service), are treated, with transient solutions obtained using the randomization technique. The exact models are compared with the approximate Dyna-METRIC model which assumes an infinite population of components and ample repair capacity.     

On the availability of R out of N repairable systems

An R out of N repairable system consisting of N components and operates if at least R components are functioning. Repairable means that failed components are repaired, and upon repair completion they are as good as new. We derive formulas for the expected up‐time, expected down‐time, and the availability of the system, using Markov renewal processes. We assume that either the repair times of the components are generally distributed and the components' lifetimes are exponential or vice versa. The analysis is done for systems with either cold or warm stand‐by. Numerical examples are given for several life time and repair time distributions. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 483–498, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10025     

A new outranking‐based approach for assigning alternatives to ordered classes

We consider the problem of assigning alternatives evaluated on several criteria into ordered categories C₁,C₂,…,C_p. This problem is known as the multi‐criteria sorting problem and arises in many situations such as classifying countries into different risk levels based on economical and socio‐political criteria, evaluating credit applications of bank customers. We are interested in sorting methods that are grounded on the construction of outranking relations. Among these, the Electre Tri method requires defining multidimensional profiles that represent the “frontier” separating consecutive categories C_h and C_h+1, and assigns an alternative to categories according to how it compares to each of the profiles. The explicit specification of the profiles of consecutive categories can be difficult for decision makers. We develop a new outranking based sorting method that does not require the explicit definition of profiles. We instead require the decision maker to assign a subset of reference alternatives to the categories. To assign the remaining alternatives, each such alternative is compared to reference alternatives, and assigned to categories accordingly. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

On computing the expected discounted return in a markov chain

The discounted return associated with a finite state Markov chain X₁, X₂… is given by g(X₁)+ αg(X₂) + α²g(X₃) + …, where g(x) represents the immediate return from state x. Knowing the transition matrix of the chain, it is desired to compute the expected discounted return (present worth) given the initial state. This type of problem arises in inventory theory, dynamic programming, and elsewhere. Usually the solution is approximated by solving the system of linear equations characterizing the expected return. These equations can be solved by a variety of well-known methods. This paper describes yet another method, which is a slight modification of the classical iterative scheme. The method gives sequences of upper and lower bounds which converge mono-tonely to the solution. Hence, the method is relatively free of error control problems. Computational experiments were conducted which suggest that for problems with a large number of states, the method is quite efficient. The amount of computation required to obtain the solution increases much slower with an increase in the number of states, N, than with the conventional methods. In fact, computational time is more nearly proportional to N², than to N³.     

A general treatment of upper unbounded and bounded hitchcock problems

This paper is designed to treat (a) the problem of the determination of the absolute minimum cost, with the associated assignments, when there is no limit, N, on the number of parcels available for shipment in a modified Hitchcock problem. This is accomplished with the use of a transformed cost matrix. C*, to which the so-called transportation paradox does not apply. The general Hitchcock solution using C* gives the cost T*, which is the absolute minimum cost of the original problem, as well as sets of assignments which are readily transformed to give the general assignments of the original problem. The sum of these latter assignments gives the value of N_u, the unbounded N for minimum cost. In addition, this paper is designed to show (b) how the method of reduced matrices may be used, (c) how a particular Hitchcock solution can be used to determine a general solution so that one solution using C* can provide the general answer, (d) how the results may be modified to apply to problems with fixed N, and hence (e) to determine the function of the decreasing T as N approaches N_u, and finally (f) to provide a treatment when the supplies at origin i and/or the demands at destination j, are bounded.     

Scheduling multiple products on parallel machines with setup costs

We consider a class of production scheduling models with m identical machines in parallel and k different product types. It takes a time p_i to produce one unit of product type i on any one of the machines. There is a demand stream for product type i consisting of n_i units with each unit having a given due date. Before a machine starts with the production of a batch of products of type i a setup cost c is incurred. We consider several different objective functions. Each one of the objective functions has three components, namely a total setup cost, a total earliness cost, and a total tardiness cost. In our class of problems we find a relatively large number of problems that can be solved either in polynomial time or in pseudo‐polynomial time. The polynomiality or pseudo‐polynomiality is achieved under certain special conditions that may be of practical interest; for example, a regularity pattern in the string of due dates combined with earliness and tardiness costs that are similar for different types of products. The class of models we consider includes as special cases discrete counterparts of a number of inventory models that have been considered in the literature before, e.g., Wagner and Whitin (Manage Sci 5 (1958), 89–96) and Zangwill (Oper Res 14 (1966), 486–507; Manage Sci 15 (1969), 506–527). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Parallel machine scheduling with eligibility constraints: A composite dispatching rule to minimize total weighted tardiness

We study a parallel machine scheduling problem, where a job j can only be processed on a specific subset of machines M_j, and the M_j subsets of the n jobs are nested. We develop a two‐phase heuristic for minimizing the total weighted tardiness subject to the machine eligibility constraints. In the first phase, we compute the factors and statistics that characterize a problem instance. In the second phase, we propose a new composite dispatching rule, the Apparent Tardiness Cost with Flexibility considerations (ATCF) rule, which is governed by several scaling parameters of which the values are determined by the factors obtained in the first phase. The ATCF rule is a generalization of the well‐known ATC rule which is very widely used in practice. We further discuss how to improve the dispatching rule using some simple but powerful properties without requiring additional computation time, and the improvement is quite satisfactory. We apply the Sequential Uniform Design Method to design our experiments and conduct an extensive computational study, and we perform tests on the performance of the ATCF rule using a real data set from a large hospital in China. We further compare its performance with that of the classical ATC rule. We also compare the schedules improved by the ATCF rule with what we believe are Near Optimal schedules generated by a general search procedure. The computational results show that especially with a low due date tightness, the ATCF rule performs significantly better than the well‐known ATC rule generating much improved schedules that are close to the Near Optimal schedules. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 249–267, 2017     

A note on scheduling parallel machines subject to breakdown and repair

In this paper we consider n jobs and a number of machines in parallel. The machines are identical and subject to breakdown and repair. The number may therefore vary over time and is at time t equal to m(t). Preemptions are allowed. We consider three objectives, namely, the total completion time, ∑ C_j, the makespan C_max, and the maximum lateness L_max. We study the conditions on m(t) under which various rules minimize the objective functions under consideration. We analyze cases when the jobs have deadlines to meet and when the jobs are subject to precedence constraints. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

A bivariate optimal replacement policy for a cold standby repairable system with repair priority

In this article, an optimal replacement policy for a cold standby repairable system consisting of two dissimilar components with repair priority is studied. Assume that both Components 1 and 2, after repair, are not as good as new, and the main component (Component 1) has repair priority. Both the sequence of working times and that of the components'repair times are generated by geometric processes. We consider a bivariate replacement policy (T,N) in which the system is replaced when either cumulative working time of Component 1 reaches T, or the number of failures of Component 1 reaches N, whichever occurs first. The problem is to determine the optimal replacement policy (T,N)* such that the long run average loss per unit time (or simply the average loss rate) of the system is minimized. An explicit expression of this rate is derived, and then optimal policy (T,N)* can be numerically determined through a two‐dimensional‐search procedure. A numerical example is given to illustrate the model's applicability and procedure, and to illustrate some properties of the optimal solution. We also show that if replacements are made solely on the basis of the number of failures N, or solely on the basis of the cumulative working time T, the former class of policies performs better than the latter, albeit only under some mild conditions. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Exact analysis of (R,s, S) inventory control systems with lost sales and zero lead time

We study an (R, s, S) inventory control policy with stochastic demand, lost sales, zero lead‐time and a target service level to be satisfied. The system is modeled as a discrete time Markov chain for which we present a novel approach to derive exact closed‐form solutions for the limiting distribution of the on‐hand inventory level at the end of a review period, given the reorder level (s) and order‐up‐to level (S). We then establish a relationship between the limiting distributions for adjacent values of the reorder point that is used in an efficient recursive algorithm to determine the optimal parameter values of the (R, s, S) replenishment policy. The algorithm is easy to implement and entails less effort than solving the steady‐state equations for the corresponding Markov model. Point‐of‐use hospital inventory systems share the essential characteristics of the inventory system we model, and a case study using real data from such a system shows that with our approach, optimal policies with significant savings in inventory management effort are easily obtained for a large family of items.     

Stochastic control of queueing systems

Suppose that the state of a queueing system is described by a Markov process { Y_t, t ≥ 0}, and the profit from operating it up to a time t is given by the function f(Y_t). We operate the system up to a time T, where the random variable T is a stopping time for the process Yt. Optimal stochastic control is achieved by choosing the stopping time T that maximizes Ef(Y_T) over a given class of stopping times. In this paper a theory of stochastic control is developed for a single server queue with Poisson arrivals and general service times.     

Selecting review periods for a coordinated multi‐item inventory model with staggered deliveries

Consider an N‐item, periodic review, infinite‐horizon, undiscounted, inventory model with stochastic demands, proportional holding and shortage costs, and full backlogging. For 1 ≤ j ≤ N, orders for item j can arrive in every period, and the cost of receiving them is negligible (as in a JIT setting). Every T_j periods, one reviews the current stock level of item j and decides on deliveries for each of the next T_j periods, thus incurring an item‐by‐item fixed cost k_j. There is also a joint fixed cost whenever any item is reviewed. The problem is to find review periods T₁, T₂, …, T_N and an ordering policy satisfying the average cost criterion. The current article builds on earlier results for the single‐item case. We prove an optimal policy exists, give conditions where it has a simple form, and develop a branch and bound algorithm for its computation. We also provide two heuristic policies with O(N) computational requirements. Computational experiments indicate that the branch and bound algorithm can handle normal demand problems with N ≤ 10 and that both heuristics do well for a wide variety of problems with N ranging from 2 to 200; moreover, the performance of our heuristics seems insensitive to N. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48:430–449, 2001     

The single server queue in discrete time-numerical analysis I

This is the first of a sequence of papers dealing with the computational aspects of the transient behavior of queues in discrete time It is shown that for a substantial class of queues of practical interest, a wealth of numerical information may be obtained by relatively unsophisticated methods This approach should prove useful in the analysis of unstable queues which operate over a limited time interval, but is by no means limited to such queues Mathematically the service unit is modeled in terms of a multivariate Markov chain, whose particular structure is used in iterative computation. Many important queue features may then be derived from the n-step transition probabilities of this chain.     

Optimal control of a production‐inventory system with both backorders and lost sales

We consider the optimal control of a production inventory‐system with a single product and two customer classes where items are produced one unit at a time. Upon arrival, customer orders can be fulfilled from existing inventory, if there is any, backordered, or rejected. The two classes are differentiated by their backorder and lost sales costs. At each decision epoch, we must determine whether or not to produce an item and if so, whether to use this item to increase inventory or to reduce backlog. At each decision epoch, we must also determine whether or not to satisfy demand from a particular class (should one arise), backorder it, or reject it. In doing so, we must balance inventory holding costs against the costs of backordering and lost sales. We formulate the problem as a Markov decision process and use it to characterize the structure of the optimal policy. We show that the optimal policy can be described by three state‐dependent thresholds: a production base‐stock level and two order‐admission levels, one for each class. The production base‐stock level determines when production takes place and how to allocate items that are produced. This base‐stock level also determines when orders from the class with the lower shortage costs (Class 2) are backordered and not fulfilled from inventory. The order‐admission levels determine when orders should be rejected. We show that the threshold levels are monotonic (either nonincreasing or nondecreasing) in the backorder level of Class 2. We also characterize analytically the sensitivity of these thresholds to the various cost parameters. Using numerical results, we compare the performance of the optimal policy against several heuristics and show that those that do not allow for the possibility of both backordering and rejecting orders can perform poorly.© 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

一类马尔可夫人才系统中的工龄和职龄

用马尔可夫模型研究人才系统中工龄和职龄问题的一般方法都要按职务等级、工龄或职龄来划分系统状态。本文在只以职务等级划分系统状态的一类无降级且逐级晋升的齐次马尔可夫人才系统中讨论了工龄和职龄问题,得到直观描述工龄和职龄的计算结果,并通过一实例说明了本方法的应用价值。     

基于隐马尔可夫模型的IDS程序行为异常检测

提出一种新的基于隐马尔可夫模型的程序行为异常检测方法,此方法利用系统调用序列,并基于隐马尔可夫模型来描述程序行为,根据程序行为模式的出现频率对其进行分类,并将行为模式类型同隐马尔可夫模型的状态联系在一起。由于各状态对应的观测值集合互不相交,模型训练中采用了运算量较小的序列匹配方法,与传统的Baum Welch算法相比,训练时间有较大幅度的降低。考虑到模型中状态的特殊含义以及程序行为的特点,将加窗平滑后的状态序列出现概率作为判决依据。实验表明,此方法具有很高的检测准确性,其检测效率也优于同类方法。     

Evaluating cost and reliability integrated performance of stochastic logistics systems

The significance of integrating reliability into logistics performance has been established [The Logistics Performance Index and Its Indicators, World Bank International Trade and Transport Departments, (2010)]. Hence, as a response to the work by the World Bank, the present article aims to evaluate the performance index R_b,d of logistics systems as the probability that a specified demand d can be distributed successfully through multistate arc capacities from the source to the destination under the constraint that the total distribution cost should not exceed the cost limitation b. This article provides a pioneering approach for a straightforward computation of the performance index R_b,d. The proposed algorithm is a hybrid between the polynomial time capacity‐scaling algorithm, which was presented by Edmonds and Karp [JACM 19 (1972)], and the decomposition algorithm, which was presented by Jane and Laih [IEEE (2008)]. Currently, the proposed approach is the only algorithm that can directly compute R_b,d. An illustration of the proposed algorithm is presented. The results of the computational experiments indicate that the presented algorithm outperforms existing algorithms. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

The NBUL class of life distribution and replacement policy comparisons

Let X and X_τ denote the lifetime and the residual life at age τ of a system, respectively. X is said to be a NBUL random variable if X_τ is smaller than X in Laplace order, i.e., X_τ ≤_L X. We obtain some characterizations for this class of life distribution by means of the lifetime of a series system and the residual life at random time. We also discuss preservation properties for this class of life distribution under shock models. Finally, under the assumption that the lifetimes have the NBUL property, we make stochastic comparisons between some basic replacement policies. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 578–591, 2001.     

Single batch machine scheduling with deliveries

We consider the problem of scheduling a set of n jobs on a single batch machine, where several jobs can be processed simultaneously. Each job j has a processing time p_j and a size s_j. All jobs are available for processing at time 0. The batch machine has a capacity D. Several jobs can be batched together and processed simultaneously, provided that the total size of the jobs in the batch does not exceed D. The processing time of a batch is the largest processing time among all jobs in the batch. There is a single vehicle available for delivery of the finished products to the customer, and the vehicle has capacity K. We assume that K = rD, where and r is an integer. The travel time of the vehicle is T; that is, T is the time from the manufacturer to the customer. Our goal is to find a schedule of the jobs and a delivery plan so that the service span is minimized, where the service span is the time that the last job is delivered to the customer. We show that if the jobs have identical sizes, then we can find a schedule and delivery plan in time such that the service span is minimum. If the jobs have identical processing times, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most 11/9 times the optimal service span. When the jobs have arbitrary processing times and arbitrary sizes, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most twice the optimal service span. We also derive upper bounds of the absolute worst‐case ratios in both cases. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 470–482, 2015