Multi-Item Scheduling by Benders' Decomposition

Scheduling the production of several items requires the determination of production quantities in different periods in the presence of resource constraints. Several approximate and heuristic algorithms have been proposed to solve this problem. However, no method for finding an optimal solution has as yet been developed. It is shown that the problem may be solved advantageously using Benders' decomposition. The subproblem in Benders' decomposition is shown to be a transportation problem, and some strategies for solving the master problem are indicated. The paper concludes with a sample problem demonstrating the application of the method.     

Multicommodity Flow Problem with Variable Arcs Capacities

The problem of maximizing the sum of the flows of all commodities in a network where the capacities of some arcs can be increased by integer numbers within a fixed budget is solved in this paper. Benders' technique is used to decompose the problem. Then Rosen's primal partitioning and non-linear duality theory are used to solve the subproblems generated by the Benders' decomposition. An application of a multicommodity network to the defence problem is mentioned.     

Characterization of local solutions for a class of nonconvex programs

A nonconvex programming problem, which arises in the context of application of Benders' decomposition procedure to a class of network optimization problems, is considered. Conditions which are both necessary and sufficient for a local maximum are derived. The concept of a basic local maximum is introduced, and it is shown that there is a finite number of basic local maxima and at least one such local maximum is optimal.     

Optimal solution of cellular manufacturing system design: Benders' decomposition approach

In this paper, a mathematical model for cellular manufacturing system (CMS) design which incorporates three critical aspects - resource utilization, alternate routings, and practical constraints, is presented. The model is shown to be NP-complete. A linear, mixed-integer version of the model which not only has fewer integer variables compared to most other models in the literature, but one that also permits us to solve it optimally using Benders' decomposition approach is presented. Some results that allow us to solve the problem efficiently as well as computational results with Benders' decomposition algorithm and a modified version are presented.     

A Profit-maximizing Plant-loading Model with Demand Fill-rate Constraints

This paper discusses a new formulation of a class of plant product-mix loading problems which are characterized by capacitated production facilities, demand fill-rate requirements, fixed facility costs, concave variable production costs and an integrated network structure which encompasses inbound supply and outbound distribution flows. In particular, we are interested in assigning product lines and volumes to a set of capacitated plants under the demand fill-rate constraints. Fixed costs are incurred when a product line is assigned to a plant. The variable production-cost function also exhibits concavity with respect to each product-line volume. Thus both scale economies and plant focus effect are considered explicitly in the model. The model also can be used to determine which market to serve in order to best allocate the firm's resources. The problem formulation leads to a concave mixed-integer mathematical programme. Given the state of the art of non-linear programming techniques, it is often not possible to find global optima for reasonably sized problems. We develop an optimization algorithm within the framework of Benders' decomposition for the case of a piecewise linear concave cost function. Our algorithm generates optimal solutions efficiently.     

Enhancing management's understanding of operational research models

The problem of the gap between management's understanding of a model and the model builder's insight is a large one. This problem continues to challenge the practice of operational research and plague contemporary modelling efforts. This paper offers an approach to enhancing a manager's understanding of the model with respect to an application. It sets out a procedure whereby (a) the reasons for the management's judgements are uncovered, and (b) the sources of disagreement with the recommendations obtained from the model are identified. The manager, learning from the model, may then change his or her judgements. Alternatively, the model builder may modify the model parameters or assumptions, leading to convergent understanding. The procedure is based on the framework of social judgement theory. An illustrative example is offered in the context of facility planning in the cement manufacturing industry.     

Experiments with an interactive procedure for MOLP given weak orders on variables and objectives

In this paper we describe computational experiments with an interactive procedure for solving a multiobjective linear-programming model. The point of departure for this paper is the work described in Gass and Dror [4] and Dror and Gass [1] in which an interactive solution procedure is outlined. Here we describe improvements in the original procedure, as well as computational experiments, and demonstrate the procedure's ability to explore successfully the solution space of a multiobjective problem.     

A fast feasibility test for relocation problems

This paper formulates a relocation model for application to redeveloping housing projects, reallocating space in office buildings and other problems. We present a fast feasibility test for this problem, demonstrate the procedure with an example, prove that the method is correct, and note the relationship of relocation feasibility to Johnson's scheduling problem.     

A fuzzy-linguistic approach to a multi-criteria sequencing problem

In this paper, a fuzzy approach to a single machine scheduling problem is considered. In this approach, the system's variables are defined using linguistic terms. Each of these variables may take values described via fuzzy triangular numbers. The scheduling criteria are the common due date, the total earliness and tardiness and the controllable duration of the jobs' processing times. The aim is to determine the length of the processing times, to sequence the jobs in the machine and, finally, to determine the common due date in a near optimal way. The problem is solved using an algorithmic procedure, which is illustrated by means of an example.     

The selection and scheduling of telecommunication calls with time windows

We consider the bandwidth scheduling problem that consists of selecting and scheduling calls from a list of available calls to be routed on a bandwidth-capacitated telecommunication network in order to maximize profit. Each accepted call should be routed within a permissible scheduling time window for a required duration. To author's knowledge, this study represents the first work on bandwidth scheduling with time windows. We present an integer programming formulation of the problem. We also propose a solution procedure based on the well-established Lagrangean relaxation technique. The results of extensive computational experiments over a wide range of problem structures indicate that the procedure is both efficient and effective.     

The resource constrained project scheduling problem with multiple crashable modes: A heuristic procedure

We present a heuristic procedure for a nonpreemptive resource constrained project scheduling problem in which the duration/cost of an activity is determined by the mode selection and the duration reduction (crashing) applied within the selected mode. This problem is a natural combination of the time/cost trade-off problem and the resource constrained project scheduling problem. The objective is to determine each activity's start (finish) time, mode and duration so that the total project cost is minimized. Total project cost is the sum of all activity costs and the penalty cost for completing the project beyond its due date. We introduce a multi-pass algorithm. We report computational results with a set of 100 test problems and demonstrate the efficacy of the proposed heuristic procedure.     

Heteroscedasticity and nonnormality

In this paper we consider the problem of comparing several means under heteroscedasticity and nonnormality. By combining Huber's M-estimators with the Brown-Forsythe test , several robust procedures were developed; these procedures were compared through computer simulation studies with-the Tan-Tabatabai procedure which was developed by combining Tiku's MML estimators with the Brown-Forsythe test . The numerical results indicate clearly that the Tan-Tabatabai procedure is considerably more powerful than tests based on Huber's M-estimators over a wide range of nonnormal distributions     

Classical solutions to phase transition problems are smooth

We prove that classical C¹–solutions to phase transition problems, which include the two–phase Stefan problem, are smooth. The problem is reduced to a fixed domain using von Mises variables. The estimates are obtained by frozen coefficients and new L_p estimates for linear parabolic equations with dynamic boundary condition. Crucial ingredients are the observation that a certain function is a Fourier multiplier, an approximation procedure of norms in Besov spaces and Meyer' approach to Nemytakij operators.     

Stabilization of Mehrotra's primal–dual algorithm and its implementation

In this paper we apply a stabilization procedure proposed by Kovačević-Vujčić and Ašić to the Mehrotra's primal–dual interior-point algorithm for linear programming. Transformations of the dual problem corresponding to the stabilization procedure are considered. The stabilization procedure and Mehrotra's algorithm are implemented in the package MATHEMATICA. A number of highly degenerate test examples are used to compare the modified Mehrotra's method with respect to the original one and the codes PCx, LIPSOL and MOSEK. We also provide numerical results on some examples from the Netlib test set.     

Optimal supplier choice with discounting

This paper investigates a model for pricing the demand for a set of goods when suppliers operate discount schedules based on total business value. We formulate the buyers's decision problem as a mixed binary integer program, which is a generalization of the capacitated facility location problem (CFLP). A branch and bound (BnB) procedure using Lagrangean relaxation and subgradient optimization is developed for solving large-scale problems that can arise when suppliers’ discount schedules contain multiple price breaks. Results of computer trials on specially adapted large benchmark instances of the CFLP confirm that a sub-gradient optimization procedure based on Shor and Zhurbenko's r-algorithm, which employs a space dilation in the direction of the difference between two successive subgradients, can be used efficiently for solving the dual problem at any node of the BnB tree.     

A Hybrid High-Order Markov Chain Model for Computer Intrusion Detection

A hybrid model based mostly on a high-order Markov chain and occasionally on a statistical-independence model is proposed for profiling command sequences of a computer user in order to identify a “signature behavior” for that user. Based on the model, an estimation procedure for such a signature behavior driven by maximum likelihood (ML) considerations is devised. The formal ML estimates are numerically intractable, but the ML-optimization problem can be substituted by a linear inverse problem with positivity constraint (LININPOS), for which the EM algorithm can be used as an equation solver to produce an approximate ML-estimate. The intrusion detection system works by comparing a user's command sequence to the user's and others' estimated signature behaviors in real time through statistical hypothesis testing. A form of likelihood-ratio test is used to detect if a given sequence of commands is from the proclaimed user, with the alternative hypothesis being a masquerader user. Applying the model to real-life data collected from AT&T Labs–Research indicates that the new methodology holds some promise for intrusion detection.     

Combined mollification—future temperatures procedure for solution of inverse heat conduction problem

The inverse heat conduction problem involves the calculation of surface heat flux and/or temperature histories from transient, measured temperatures inside solids. This paper proposes and investigates a new combined procedure that is based on two different methods: a data filtering interpretation of the mollification method and Beck's future temperature method. A test case is investigated of a semi-infinite body exposed to a heat flux that is initially zero, has a unit increase, an then drops to zero. The combined procedure is shown to be accurate and stable with respect to perturbations in the data even for small dimensionless time steps. The future temperatures method can be significantly improved upon by the combined procedure.     

Dynamical stability of an elastic column and the phenomenon of bifurcation

The article studies the stability of rectilinear equilibrium shapes of a non-linear elastic thin rod (column or Timoshenko's beam), the ends of which are pressed. Stability is studied by means of the Lyapunov direct method with respect to certain integral characteristics of the type of norms in Sobolev spaces. To obtain equations of motion, a model suggested in [16] is used. Furta [6] solved the problem of stability for all values of the parameter except bifurcational ones. When values of the system's parameter become bifurcational, the study of stability is more complicated already in a finite-dimensional case. To solve a problem like that, one often has to use a procedure of solving the singularities described in [1], for example. In this paper a change of variables is made which, in fact, is the first step of the procedure mentioned. To prove instability, we use a Chetaev function which can be considered as an infinite-dimensional analogue of functions suggested in [14, 9]. The article also investigates a linear problem on the stability of adjacent shapes of equilibrium when the parameter has supercritical values (post-buckling).