A note on the complexity of flow shop scheduling with transportation constraints

This note investigates two-machine flow shop scheduling with transportation constraints to minimize makespan. Recently, Soukhal et al. [A. Soukhal, A. Oulamara, P. Martineau, Complexity of flow shop scheduling problems with transportation constraints, European Journal of Operational Research 161 (2005) 32–41] proved that this problem is strongly NP-hard when the capacity of the truck is limited to two or three parts. The considered problem with blocking constraints is also proved to be strongly NP-hard by Soukhal et al. Unfortunately, their proofs contain mistakes. We point out their proofs’ invalidity and then show that, when the capacity of the truck is limited to two parts, the problem is binary NP-hard, and when the capacity of the truck is limited to three parts the problem is strongly NP-hard even if the jobs have a common processing time on machine one and all jobs have the same transportation time. We show also that the last result can be generalized to any fixed c (c ? 3) parts.     

New reformulations for probabilistically constrained quadratic programs

The mixed integer quadratic programming (MIQP) reformulation by Zheng, Sun, Li, and Cui (2012) for probabilistically constrained quadratic programs (PCQP) recently published in EJOR significantly dominates the standard MIQP formulation ( and ) which has been widely adopted in the literature. Stimulated by the dimensionality problem which Zheng et al. (2012) acknowledge themselves for their reformulations, we study further the characteristics of PCQP and develop new MIQP reformulations for PCQP with fewer variables and constraints. The results from numerical tests demonstrate that our reformulations clearly outperform the state-of-the-art MIQP in Zheng et al. (2012).     

An improved solution to the replenishment policy for the EMQ model with rework and multiple shipments

Recently, Chiu et al. (2012) [1] present an alternative optimization procedure to derive the optimal replenishment lot size for an economic manufacturing quantity (EMQ) model with rework and multiple shipments. This inventory model was proposed by Chiu et al. (2011) [2]. Both papers do not consider the determining of the number of shipments. This paper determines both the optimal replenishment lot size and the optimal number of shipments jointly. The solution of this paper is better than the solutions of Chiu et al.  and .     

Recursive algorithm for the reliability of a connected-(1, 2)-or-(2, 1)-out-of-(m, n):F lattice system

The connected-(1, 2)-or-(2, 1)-out-of-(m, n):F lattice system is included by the connected-X-out-of-(m, n):F lattice system defined by Boehme et al. [Boehme, T.K., Kossow, A., Preuss, W., 1992. A generalization of consecutive-k-out-of-n:F system. IEEE Transactions on Reliability 41, 451–457]. This system fails if and only if at least one subset of connected failed components occurs which includes at least a (1, 2)-matrix (that is, a row and two columns) or a (2, 1)-matrix(that is, two rows and a column) of failed components. This system is applied to two-dimensional network problems with adjacent constraints, and various systems, for example, a supervision system, etc.     

An acquisition policy for a single item multi-supplier system with real-world constraints

This paper proposes an exact acquisition policy for solving the single-item multi-supplier problem with real-world constraints. Compared with the model of Rosenblatt et al. [Note. An acquisition policy for a single item multi-supplier system, Manage. Sci. 44 (1998) S96–S100], the proposed method has contributions in that the global optimal solutions can be obtained to indicate the best acquisition policy, and real-world constraints can easily be added as appropriate for real-world situations. In addition, the benefits of price-quantity discount (PQD) under conditions of the single item muti-supplier system are also considered in the paper.     

Problem F2∥Cmax with forbidden jobs in the first or last position is easy

Saadani et al. [N.E.H. Saadani, P. Baptiste, M. Moalla, The simple F2∥C_max with forbidden tasks in first or last position: A problem more complex that it seems, European Journal of Operational Research 161 (2005) 21–31] studied the classical n-job flow shop scheduling problem F2∥C_max with an additional constraint that some jobs cannot be placed in the first or last position. There exists an optimal job sequence for this problem, in which at most one job in the first or last position is deferred from its position in Johnson’s [S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly 1 (1954) 61–68] permutation. The problem was solved in O(n²) time by enumerating all candidate job sequences. We suggest a simple O(n) algorithm for this problem provided that Johnson’s permutation is given. Since Johnson’s permutation can be obtained in O(n log n) time, the problem in Saadani et al. (2005) can be solved in O(n log n) time as well.     

Linear flows and Morse graphs: Topological consequences in low dimensions

The main aim of this paper is to show some specific connections between linear dynamic and graphs. Precisely, the Morse decomposition of a linear flow on the Grassmannians induces a directed graph. We apply the results appearing in Ayala et al. (2006, 2005)  and  and Colonius et al. (2002) [4] and compute the associated graphs for linear flows in dimensions two and three.     

AnO(\sqrt n L) iteration bound primal-dual cone affine scaling algorithm for linear programmingiteration bound primal-dual cone affine scaling algorithm for linear programming

In this paper we introduce a primal-dual affine scaling method. The method uses a search-direction obtained by minimizing the duality gap over a linearly transformed conic section. This direction neither coincides with known primal-dual affine scaling directions (Jansen et al., 1993; Monteiro et al., 1990), nor does it fit in the generic primal-dual method (Kojima et al., 1989). The new method requires main iterations. It is shown that the iterates follow the primal-dual central path in a neighbourhood larger than the conventional neighbourhood. The proximity to the primal-dual central path is measured by trigonometric functions.     

The asymmetric travelling salesman problem and a reformulation of the Miller–Tucker–Zemlin constraints

In this paper we compare the linear programming (LP) relaxations of several old and new formulations for the asymmetric travelling salesman problem (ATSP). The main result of this paper is the derivation of a compact formulation whose LP relaxation is characterized by a set of circuit inequalities given by Grotschel and Padberg (In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A., Shmoys, D.B. (Eds.), The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, New York, 1985). The new compact model is an improved and disaggregated version of a well-known model for the ATSP based on the subtour elimination constraints (Miller et al., Journal of ACM 7 (1960) 326–329). The circuit inequalities are weaker than the subtour elimination constraints given by Dantzig et al. However, each one of these circuit inequalities can be lifted into several different facet defining inequalities which are not dominated by the subtour elimination inequalities. We show that some of the inequalities involved in the previously mentioned compact formulation can be lifted in such a way that, by projection, we obtain a small subset of the so-called D_k^← and D_k^→ inequalities. This shows that the LP relaxation of our strongest model is not dominated by the LP relaxation of the model presented by Dantzig et al. (Operations Research 2 (1954) 393–410). The new models motivate a new classification of formulations for the ATSP.     

A Stochastic Model for Assessing Synchronization among Spike Trains in a Population of Motor Neurons

Synchronization among discharges in a population of motor neurons is of interest because of its potential to characterize physiological changes related to the neuromuscular system. Milner-Brown et al. (1973) developed a method to quantify synchronization in a population of motor neurons, in which synchronization is measured by averaging the spike-triggered surface electromyograms (EMG) waveforms. The surface EMG method opened a way to assess motor neuron synchrony in a large population of motor neurons instead of only a few, allowed investigators to track the same or similar groups of motor neurons longitudinally, and overcame the limit of examining only a few motor neurons using cross correlation. However, experimental results have suggested that the surface EMG method does not accurately and consistently detect motor neuron synchrony under some experimental conditions (Yue et al., 1995). This article reports our attempts to improve this method by establishing a new mathematical framework for the surface EMG procedure and to propose a general model based on this framework. The proposed model includes existing methods such as that of Hamm et al. (1985) as special cases. Based on the proposed model, we proposed a new synchronization index and performed computer simulation that indicated that the new index detects synchronization consistently with relatively high accuracy. Though based on the neuromuscular system, the proposed model should be extendable for detecting synchronization in other nervous systems.     

Notes on a new approximate solution of 2-D heat equation backward in time

In this paper, we consider a backward heat problem that appears in many applications. This problem is ill-posed. The solution of the problem as the solution exhibits unstable dependence on the given data functions. Using a new regularization method, we regularize the problem and get some new error estimates. Some numerical tests illustrate that the proposed method is feasible and effective. This work is a generalization of many recent papers, including the earlier paper [A new regularized method for two dimensional nonhomogeneous backward heat problem, Appl. Math. Comput. 215(3) (2009) 873–880] and some other authors such as Chu-Li Fu et al. ,  and , Campbell et al. [4].     

A (0–1) goal programming model for scheduling the tour of a marketing executive

This paper addresses the problem of scheduling the tour of a marketing executive (ME) of a large electronics manufacturing company in India. In this problem, the ME has to visit a number of customers in a given planning period. The scheduling problem taken up in this study is different from the various personnel scheduling problems addressed in the literature. This type of personnel scheduling problem can be observed in many other situations such as periodical visits of inspection officers, tour of politicians during election campaigns, tour of mobile courts, schedule of mobile stalls in various areas, etc. In this paper the tour scheduling problem of the ME is modeled using (0–1) goal programming (GP). The (0–1) GP model for the data provided by the company for 1 month has 802 constraints and 1167 binary variables. The model is solved using LINDO software package. The model takes less than a minute (on a 1.50 MHz Pentium machine with 128 MB RAM) to get a solution of the non-preemptive version and about 6 days for the preemptive version. The main contribution is in problem definition and development of the mathematical model for scheduling the tour.     

An approximately global optimization method for assortment problems

Assortment problems occur when we want to cut a number of small rectangular pieces from a large rectangle to get the minimum area within the rectangle. Recently, Chen et al. proposed a useful model for assortment problems. Although Chen et al.'s model is quite promising to find solutions, there are two inadequacies in their model: firstly, the objective function in their model is a polynomial term, which may not lead to a globally optimal solution; secondly, too many 0–1 variables are used to formulate the non-overlapping constraints. We propose a new method to reformulate an assortment model. Our model is not only able to find the approximately global optimal solution, but involves less 0–1 variables for formulating non-overlapping constraints.     

The influences of longitudinal surface roughness on sub-critical and super-critical limit cycles of short journal bearings

By applying the stochastic model of rough surfaces by Christensen (1969–1970, 1971)  and  together with the Hopf bifurcation theory by Hassard et al. (1981) [3], the present study is mainly concerned with the influences of longitudinal roughness patterns on the linear stability regions, Hopf bifurcation regions, sub-critical and super-critical limit cycles of short journal bearings. It is found that the longitudinal rough-surface bearings can exhibit Hopf bifurcation behaviors in the vicinity of bifurcation points. For fixed bearing parameter, the effects of longitudinal roughness structures provide an increase in the linear stability region, as well as a reduction in the size of sub-critical and super-critical limit cycles as compared to the smooth-bearing case.     

Approximation of signals of class Lip(α, p) by linear operators

Mittal, Rhoades [5], [6], [7] and [8] and Mittal et al. [9] and [10] have initiated a study of error estimates E_n(f) through trigonometric-Fourier approximation (tfa) for the situations in which the summability matrix T does not have monotone rows. In this paper we continue the work. Here we extend two theorems of Leindler [4], where he has weakened the conditions on {p_n} given by Chandra [2], to more general classes of triangular matrix methods. Our Theorem also partially generalizes Theorem 4 of Mittal et al. [11] by dropping the monotonicity on the elements of matrix rows, which in turn generalize the results of Quade [15].     

Alternate approaches to solving the Holt et al. model and to performing sensitivity analysis

The staircase structure of the recurrence relations for the Holt et al. model can be used to develop simple and efficient computational approaches for obtaining the optimal solution. The computational approaches are noniterative. We deal with finite planning horizon cases in which one or more terminal boundary conditions are not specified. The computation time varies linearly with the number of periods in the planning horizon. A framework is also developed for sensitivity analysis on the terminal values and for generation of alternate production plans. The alternate plans provide considerable flexibility to the decision maker because they can be evaluated in the context of (a) constraints not included in the model, (b) plant capacity, (c) actual costs, and (d) implications beyond the planning horizon. The results should be of interest for real world applications as well as for research because the Holt et al. model continues to be used as a benchmark to evaluate the performance of other aggregate production planning models.     

Contour line construction for a new rectangular facility in an existing layout with rectangular departments

In a recent paper, Savas et al. [S. Savas, R. Batta, R. Nagi, Finite-size facility placement in the presence of barriers to rectilinear travel, Operations Research 50 (6) (2002) 1018–1031] consider the optimal placement of a finite-sized facility in the presence of arbitrarily shaped barriers under rectilinear travel. Their model applies to a layout context, since barriers can be thought to be existing departments and the finite-sized facility can be viewed as the new department to be placed. In a layout situation, the existing and new departments are typically rectangular in shape. This is a special case of the Savas et al. paper. However the resultant optimal placement may be infeasible due to practical constraints like aisle locations, electrical connections, etc. Hence there is a need for the development of contour lines, i.e. lines of equal objective function value. With these contour lines constructed, one can place the new facility in the best manner. This paper deals with the problem of constructing contour lines in this context. This contribution can also be viewed as the finite-size extension of the contour line result of Francis [R.L. Francis, Note on the optimum location of new machines in existing plant layouts, Journal of Industrial Engineering 14 (2) (1963) 57–59].     

Implicit–explicit schemes for nonlinear nonlocal equations with a gradient flow structure in one space dimension

Nonlinear convection–diffusion equations with nonlocal flux and possibly degenerate diffusion arise in various contexts including interacting gases, porous media flows, and collective behavior in biology. Their numerical solution by an explicit finite difference method is costly due to the necessity of discretizing a local spatial convolution for each evaluation of the convective numerical flux, and due to the disadvantageous Courant–Friedrichs–Lewy (CFL) condition incurred by the diffusion term. Based on explicit schemes for such models devised in the study of Carrillo et al. a second‐order implicit–explicit Runge–Kutta (IMEX‐RK) method can be formulated. This method avoids the restrictive time step limitation of explicit schemes since the diffusion term is handled implicitly, but entails the necessity to solve nonlinear algebraic systems in every time step. It is proven that this method is well defined. Numerical experiments illustrate that for fine discretizations it is more efficient in terms of reduction of error versus central processing unit time than the original explicit method. One of the test cases is given by a strongly degenerate parabolic, nonlocal equation modeling aggregation in study of Betancourt et al. This model can be transformed to a local partial differential equation that can be solved numerically easily to generate a reference solution for the IMEX‐RK method, but is limited to one space dimension.     

A Point Process Approach to Filtered Processes

We consider some models of filtered point processes such as those developped in Yue and Hashino (2001), and rephrase them in terms of point processes. We derive from this formulation some estimates for the probability of overflow in a rainfall process. This method allows us by considering a non deterministic model of filtering to compute some characteristics of the compound models of Cowpertwait (1994), Phelan (1991), and Rodriguez-Iturbe et al. (1987, 1988). A spatial version of this point process is also studied, using an analogy with the boolean model of stochastic geometry we compute bounds for the probability of dryness in a compound rainfall process.