AN ITERATIVE SOLUTION SCHEME FOR SYSTEMS OF WEAKLY CONNECTED BOUNDARY ELEMENT EQUATIONS

In this paper an iterative scheme of first degree is developed for solving linear systems of equations. The systems investigated are those which are derived from boundary integral equations and are of the form ∑^N_j=1H_ijx_j=c_i, i=1, 2,…,N, where H_ij are matrices, x_j and c_i are column vectors. In addition, N denotes the number of domains and for i≠j, H_ij is considered to be small in some sense. These systems, denoted as weakly connected, are solved using first-order iterative techniques initially developed by the authors for solving single-domain problems. The techniques are extended to solve multi-domain problems. Novel solution strategies are investigated and procedures are developed which are computationally efficient. Computation times are determined for the iterative procedures and for elimination techniques indicating the benefits of iterative techniques over direct methods for problems of this nature.     

Solving probabilistic multi-facility Weber problem by vector quantization

The multi-facility Weber problem is concerned with locating in the plane m facilities having unlimited capacities and allocating them to n customers at minimum total cost. The deterministic version is a non-convex optimization problem and difficult to solve exactly. In this work we focus on a probabilistic extension and consider the situation where the customer locations are randomly distributed. For this problem, we propose new heuristics based on the principle of vector quantization which are capable of computing good quality solutions for general distance functions and customer location distributions.     

Optimization of mechanical systems: On strategy of non-linear first-order approximation

The paper presents an extended approach to non-linear first-order approximation of non-linear programming problems and it explains how to transform an approximate problem into a strictly convex one. The essence of the proposed approximation technique is to rewrite each given function h_j as a composite g_j ^o Ψ^j. The function Ψ^j has to be chosen—the paper explains how to do this—while g_j is linear approximated with g_j. The approximation of h_j is then obtained as g_j ^o Ψ^j. This approach enables one to obtain approximate functions with variable conservativeness, which implies an adjustable approximate problem. A solution procedure, which replaces the original problem with a sequence of approximate problems, can therefore adjust each succeeding approximate problem to improve the convergence properties. The theory is illustrated with a three parameters controlled approximation. This technique represents, together with an optimality criteria based solution procedure, a powerful and economic tool for solving nonlinear programming problems. The three parameters, which influence to a great extent the conservativeness of the approximate functions, are under full control of the optimizer. They are varied automatically during the process of optimization to speed-up the convergence or to prevent oscillations. The benefits gained from the proposed approach are demonstrated on several numerical examples involving structures and a dynamic multibody system.     

A two‐phase approach for single machine scheduling problems: Minimizing the total absolute deviation

Abstract

This paper presents a heuristic for solving a single machine scheduling problem with the objective of minimizing the total absolute deviation. The job to be scheduled on the machine has a processing time, p_i , and a preferred due date, d_i . The total absolute deviation is defined as the sum of the earliness or tardiness of each job on a schedule 5. This problem is proved to be NP‐complete by Garey et al. [8]. As a result, we developed a two‐phase procedure to provide a near‐optimal solution to this problem. The two‐phase procedure includes the following steps: First, a greedy heuristic is applied to the set of jobs, N, to generate a “good” initial sequence. According to this initial sequence, we run Garey's local optimization algorithm to provide an initial schedule. Then, a pairwise switching algorithm is adopted to further reduce the total deviation of the schedule. The effectiveness of the two‐phase procedure is empirically evaluated and has been found to indicate that the solutions obtained from this heuristic procedure are often better than other heuristic approaches.     

A data mining approach to optimise shelf space allocation in consideration of customer purchase and moving behaviours

A good shelf space allocation strategy can help customers easily find product items and dramatically increase store profit. Previous studies generally relied on the space elasticity formula to optimise space allocation models, but space elasticity requires estimates of many parameters, resulting in high costs and frequent errors in the mathematical models. In this study, a three-stage data mining method is proposed for solving the shelf space allocation problem with consideration of both customer purchase and moving behaviours. In the first stage, the customer’s purchasing behaviour is derived from records of previous transactions, while moving behaviour is collected through radio frequency identification systems. In the second stage, the A priori algorithm is applied to obtain frequent product association rules from purchase transactions. In addition, the UMSP_L algorithm is adopted to derive high-utility mobile sequential patterns from customer mobile transaction sequences. In the third stage, all product items are classified as either major, minor or trivial according to a set of criteria. A Location preference evaluation procedure is then developed to calculate location preference if a minor item is placed at a given section of the store. Based on the location preference matrix, minor items are reassigned to optimal shelves. The experimental results show the proposed method can reassign items to suitable shelves and dramatically increase cross-selling opportunities for major and minor items.     

Multi-objective short-term production scheduling for open-pit mines: a hierarchical decomposition-based algorithm

This article presents a novel algorithm for solving a short-term open-pit production-scheduling problem in which several objectives, of varying priority, characterize the quality of each solution. A popular approach employs receding horizon control, dividing the horizon into N period-aggregates of increasing size (number of periods or span). An N-period mixed integer program (MIP) is solved for each period in the original horizon to incrementally construct a production schedule one period at a time. This article presents a new algorithm that, in contrast, decomposes the horizon into N period-aggregates of equal size. Given a schedule for these N periods, obtained by solving an N-period MIP, the first of these aggregates is itself decomposed into an N-period scheduling problem with guidance provided on what regions of the mine should be extracted. The performance of this hierarchical decomposition-based approach is compared with that of receding horizon control on a suite of data sets generated from an operating mine producing millions of tons of ore annually. As the number of objectives being optimized increases, the hierarchical decomposition-based algorithm outperforms receding horizon control, in a majority of instances.     

On Intrinsic Bounds in the Nullstellensatz

 Let k be a field and  f ₁, . . . ,  f _s be non constant polynomials in k[X ₁, . . . , X _n ] which generate the trivial ideal. In this paper we define an invariant associated to the sequence  f ₁, . . . ,  f _s : the geometric degree of the system. With this notion we can show the following effective Nullstellensatz: if δ denotes the geometric degree of the trivial system  f ₁, . . . ,  f _s and d :=max _j  deg( f _j ), then there exist polynomials p ₁, . . . , p _s ∈k[X ₁, . . . , X _n ] such that 1=∑ _j  p _j  f _j and deg p _j   f _j ≦3n ²δd. Since the number δ is always bounded by (d+1) ^n-1 , one deduces a classical single exponential upper bound in terms of d and n, but in some cases our new bound improves the known ones. Received November 24, 1995, revised version January 19, 1996     

Optimal production plan for a multi-products manufacturing system with production rate dependent failure rate

This study deals with the problem of dependence between production and failure rates in the context of a multi-product manufacturing system. It provides an answer about how to produce (i.e. the production rates) and what to produce (i.e. which product) over a finite horizon of H periods of equal length. We consider a single randomly failing and repairable manufacturing system producing two products P_a and P_b . The product P_a is produced to supply the strategic demand d(k) of the principal customer via a buffer stock S over k periods (k?=?1,?2,?…?,?H). The second product P_b is produced to meet a secondary but very profitable demand. It is produced during a given interval at the end of each period k. We develop a genetic algorithm to determine simultaneously the optimal production rate of the first product during each period k and the optimal duration of the production interval of the second product, maximising the total expected profit.     

Reformulations of the shortest route model for dynamic multi-item multi-level capacitated lotsizing

The shortest route representation of the dynamic multi-item multi-level capacitated lotsizing problem is appealing due to the tight bound provided by its Linear Programming (LP) relaxation. However, it suffers from two main drawbacks: Firstly, even solving the LP relaxation of problem instances with up to 16 time periods and 40 items with standard mathematical programming software might require a prohibitive amount of computer time. Secondly, the quadratic growth of the number of variables with the number of periods restricts the solution of problem instances with many periods. Both drawbacks will be addressed in this paper by proposing reformulations of the original shortest route model. Especially we will introduce a model formulation which allows theuser to find a tradeoff between model size and tightness of the lower bound obtained by the LP relaxation by specifying the number oflook ahead periods . Furthermore, we will provide an iterative procedure for determining those look ahead periods which result in the tightest LP relaxation. Theoretical insights as well as computational results are provided, too.     

Particle swarm optimization for the multi-period cross-docking distribution problem with time windows

Cross-docking has emerged as a new technique in supply chain management to replace the warehouse concept in the retail industry. This paper proposes a multi-period cross-docking distribution problem that consists of manufacturers, cross-docks and customers. This model is formulated for cases that consider multiple products, consolidation of customer orders and time windows that are available in multiple periods. The objective function is to minimise the total cost, which includes transportation cost, inventory cost and penalty cost. The penalty cost arises when demand remains in each period that cannot be satisfied. To deal with the complexity of the problem, an algorithm is developed based on particle swarm optimisation (PSO) with multiple social learning terms, GLNPSO, with two solution representations. The solution representations are a one-period solution representation (OP-SR) and a multi-period solution representation (MP-SR). The GLNPSO-based algorithm performs well in solving this problem. Moreover, both representations are proven effective when comparing the solution quality and computational time with those results obtained from CPLEX. In terms of quality, the MP-SR solution is better than the OP-SR solution for both stable and fluctuating demand instances. However, MP-SR requires more computational effort than OP-SR.     

Predicting the piezoelectric response of novel anisotropic 1–2 type composites

A model of the 1–2 type piezoelectric composite comprising zig-zag ferroelectric piezoactive ceramic inclusions in a passive polymer matrix is proposed. The orientational and concentrational profiles of the piezoelectric coefficients d _3j * and g _3j *, calculated for various sets of parameters characterizing the composite microstructure are presented. It is demonstrated that the proposed microstructure favors nonmonotonic and alternating-sign behavior of d _3j * and g _3j *. Therefore, the piezoelectric anisotropy and sensitivity of the given 1–2 type composite can be varied within broad limits.     

On bilevel machine scheduling problems

Bilevel scheduling problems constitute a hardly studied area of scheduling theory. In this paper, we summarise the basic concepts of bilevel optimisation, and discuss two problem classes for which we establish various complexity and algorithmic results. The first one is the bilevel total weighted completion time problem in which the leader assigns the jobs to parallel machines and the follower sequences the jobs assigned to each machine. Both the leader and the follower aims to minimise the total weighted completion time objective, but with different job weights. When the leader’s weights are arbitrary, the problem is NP-hard. However, when all the jobs are of unit weight for the leader, we provide a heuristic algorithm based on iterative LP-rounding along with computational results, and provide a sufficient condition when the LP-solution is integral. In addition, if the follower weights induce a monotone (increasing or decreasing) processing time order in any optimal solution, the problem becomes polynomially solvable. As a by-product, we characterise a new polynomially solvable special case of the MAX m-CUT problem, and provide a new linear programming formulation for the P||?_j C_j{P||\sum_j C_j} problem. Finally, we present some results on the bilevel order acceptance problem, where the leader decides on the acceptance of orders and the follower sequences the jobs. Each job has a deadline and if a job is accepted, it cannot be late. The leader’s objective is to maximise the total weight of accepted jobs, whereas the follower aims at minimising the total weighted job completion times. For this problem, we generalise some known single-level machine scheduling algorithms.     

MIP-based heuristics for lotsizing in capacitated pure flow shop with sequence-dependent setups

Lotsizing in capacitated pure flow shop with sequence-dependent setups has been considered in this paper. An exact formulation of the problem is provided as a mixed-integer program. It is well known that the capacitated lotsizing and scheduling problem (CLSP) is NP-hard. The introduction of serially arranged machines and sequence-dependent setups makes the problem even more complicated. Five MIP-based heuristics based on iterative procedures are provided. The first three heuristics are based on the original model but to solve non-small instances of problem, the last two heuristics are based on permutation flow shop problem which ignores the majority of combinations. To test the accuracy of heuristics, two lower bounds are developed and compared against the optimal solution. The trade-offs between solution quality and computational times of heuristics are also provided.     

An efficient optimization procedure for designing a capacitated distribution network with price-sensitive demand

This paper considers a location-allocation problem in a supply-chain distribution network with capacitated distribution centers and customers with price-sensitive demands. The problem determines location, allocation and price decisions in order to maximize the total profit under two supply policies. Serving all of the customers is compulsory under the first policy, but is optional under the second. The problem is formulated as a mixed-integer linear program and solved by a Lagrangian relaxation algorithm under each policy. The numerical study indicates that the proposed algorithms are highly efficient and effective for solving large-sized instances of the problem.     

Scheduling direct deliveries with time windows to minimise truck fleet size and customer waiting times

This paper tackles the operational problem of scheduling direct deliveries from a single source (e.g. a distribution centre) to multiple customers (e.g. assembly plants). The problem consists of scheduling a set of given round trips such that each trip is processed exactly once within its time window and the employed truck fleet is as small as possible. Moreover, as a secondary objective, customer waiting times should be minimal. Such planning problems arise in many industries like, for instance, the automotive industry, where just-in-time parts are often shipped via direct delivery to OEMs. We propose two different mixed-integer programming models for this problem, discuss similarities to classic routing and scheduling problems from the literature, identify a subproblem that is solvable in polynomial time and propose suitable heuristics. In a computational study, the proposed procedures are shown to perform well both on newly generated instances as well as those from the literature. We also show that minimising waiting times is an adequate measure to make schedules more robust in the face of unforeseen disturbances.     

Nontrivial behavior of the piezoelectric coefficients of 0–3 composites of the modified PbTiO<Subscript>3</Subscript> ceramics-polymer type

Piezoelectric properties of the 0–3 connectivity composites comprising spheroidal inclusions of modified PbTiO₃ ceramics dispersed in a polymer matrix have been studied. Monotonic and nonmonotonic concentration dependences of the effective piezoelectric coefficients e _3j *, d _3j *, h _3j *, and (j=1, 3) of the composites with elongated ferroelectric ceramic (FC) inclusions are analyzed. The observed nontrivial piezoelectric response of the 0–3 composites of the modified PbTiO₃ ceramics-polymer type is determined to a considerable extent by properties of the polymer matrix and by the sign of the e _3j ^(FC) coefficients (e _3j ^(FC) >0).     

Integrated optimization of location assignment and sequencing in multi-shuttle automated storage and retrieval systems under modified 2n-command cycle pattern

This article explores the integrated optimization problem of location assignment and sequencing in multi-shuttle automated storage/retrieval systems under the modified 2n-command cycle pattern. The decision of storage and retrieval (S/R) location assignment and S/R request sequencing are jointly considered. An integer quadratic programming model is formulated to describe this integrated optimization problem. The optimal travel cycles for multi-shuttle S/R machines can be obtained to process S/R requests in the storage and retrieval request order lists by solving the model. The small-sized instances are optimally solved using CPLEX. For large-sized problems, two tabu search algorithms are proposed, in which the first come, first served and nearest neighbour are used to generate initial solutions. Various numerical experiments are conducted to examine the heuristics’ performance and the sensitivity of algorithm parameters. Furthermore, the experimental results are analysed from the viewpoint of practical application, and a parameter list for applying the proposed heuristics is recommended under different real-life scenarios.     

A dynamic multi-item two-activity problem

Summary We consider the following symmetric generalization of the well-known asset-selling problem. Assume that there are two activities, each of which must be carried out a given number of times. An example is the disposal ofi andj containers of toxic waste of two different kinds. Exactly one of the activities is performed per time period. The random rewards (possibly negative) for performing the different tasks are i.i.d. and have a known two-dimensional joint distribution. In addition, there are fixed costsc, c ₁ andc ₂ (possibly negative) per period as long as activities of both kinds, or only of the first or only of the second kind must be performed. Based on a realization of the two random rewards, each period a choice must be made which of the two activities to perform such that the expected total reward becomes maximal. We show for arbitrary discount factor the existence of an optimal control limit policy with recursively computable critical numbersd _ij . Some explicitly solvable cases are presented. Under appropriate assumptions thed _ij 's are monotone ini and/orj which allows, despite a 4-dimensional state space, to represent the optimal policy by a family of 2-dimensional monotone decision regions. And then, the limits of thed _ij 's can be used to identify large sets of states where the optimal decision can be found without numerical computations. The basic tool is the integrated distribution function of the difference of the two rewards. The paper generalizes many of the known results on asset-selling problems without recall.     

Effect of synthesis conditions on the phase composition and critical current density of Bi1.6Pb0.4Sr2−x KxCa2Cu3F0.8Oy

Effects of the temperature-time schedule on the phase composition, critical current density j _c, critical temperature T _c, and electric resistance in the normal state (ρ) of the samples of Bi_1.6Pb_0.4Sr_2−x K_xCa₂Cu₃F_0.8O_y (x=0 or 0.02) compositions were studied by X-ray diffraction analysis and by measuring resistances and current-voltage characteristics of the samples. The values of j _c=of 583.6 A/cm² (at 77.4 K) and T _c(R=0)=107.1 K were obtained in the samples with x=0.02 upon partial fusion. In order to obtain high j _c values, the samples must be synthesized (sintered) prior to the fusion stage.     

Controlled magnetoresistance in Y<Subscript>3/4</Subscript>Lu<Subscript>1/4</Subscript>Ba<Subscript>2</Subscript>Cu<Subscript>3</Subscript>O<Subscript>7</Subscript>-CuO composites at 77 K

We have studied the low-temperature magnetoresistance of Y_3/4Lu_1/4Ba₂Cu₃O₇-CuO composites obtained by fast sintering technique and established a relation between the probing to critical current density ratio j/j _c and the shape of the magnetoresistance curve ρ(H). For j/j _c<1, the electric resistance arises at a threshold value of the magnetic field strength H _c. For j/j _c≥1, a linear variation of ρ(H) at 77 K in the range from 0 to 14 Oe can be provided by selecting the CuO content (in the 15–30 vol % interval) and the j value (in the 0.003–0.2 A/cm² range). In the latter case, the slope dρ/dH (i.e., the sensitivity of the electric resistivity with respect to the magnetic field) is 1–20 mΩ cm/Oe and the relative field-induced increase in the resistivity ρ₀=(ρ(H)−ρ(H=0))/ρ(H=0) amounts to 1320 and 685% at H=200 and 35 Oe, respectively. Composites possessing controlled magnetoresistance are promising materials for the active elements of magnetic field sensors capable of operating at a practically convenient liquid nitrogen temperature.