Algorithmic complexity of list colorings

Given a graph G = (V,E) and a finite set L(v) at each vertex v ε V, the List Coloring problem asks whether there exists a function f:V → _vεVL(V) such that (i) f(v)εL(v) for each vεV and (ii) f(u) ≠f(v) whenever u, vεV and uvεE. One of our results states that this decision problem remains NP-complete even if all of the followingconditions are met: (1) each set L(v) has at most three elements, (2) each “color” xε_vεVL(v) occurs in at most three sets L(v), (3) each vertex vεV has degree at most three, and (4) G is a planar graph. On the other hand, strengthening any of the assumptions (1)–(3) yields a polynomially solvable problem. The connection between List Coloring and Boolean Satisfiability is discussed, too.     

On optimality in an uncertain environment

The main objective of this paper is to formulate an uncertain counterpart of a minimum-norm problem in the form of primary and secondary optimization problems using the concept of uncertain norms.This work was supported partly by the Committee of Scientific Research (KBN).     

Outsourcing and capacity planning in an uncertain global environment

Firms employing offshore outsourcing strategies may face both exchange rate and demand uncertainties. In this paper, we show that the firms may benefit from operational option to switch production by keeping capacities with both domestic and foreign suppliers. The value of the operational option increases as the exchange rate uncertainty or demand uncertainty increases. In addition, when the firms become risk-averse, they may use domestic capacity to hedge against offshore capacity. As a result, the firms may choose to hold local capacity even if it exhibits negative marginal contribution to the profit. Furthermore, risk-averse firms may keep more total capacity than risk-neutral firms.     

Modelling and simulation of a supply chain in an uncertain environment

This paper describes fuzzy modelling and simulation of a supply chain (SC) in an uncertain environment, as the first step in developing a decision support system. An SC is viewed as a series of facilities that performs the procurement of raw material, its transformation to intermediate and end-products, and distribution and selling of the end-products to customers. All the facilities in the SC are coupled and interrelated in a way that decisions made at one facility affect the performance of others. SC fuzzy models and a simulator cover operational SC control. The objective is to determine the stock levels and order quantities for each inventory in an SC during a finite time horizon to obtain an acceptable delivery performance at a reasonable total cost for the whole SC. Two sources of uncertainty inherent in the external environment in which the SC operates were identified and modelled: customer demand and external supply of raw material. They were interpreted and represented by fuzzy sets. In addition to the fuzzy SC models, a special SC simulator was developed. The SC simulator provides a dynamic view of the SC and assesses the impact of decisions recommended by the SC fuzzy models on SC performance.     

Instabilities of robot motion

Instabilities of robot motion are caused by topological reasons. In this paper we find a relation between the topological properties of a configuration space (the structure of its cohomology algebra) and the character of instabilities, which are unavoidable in any motion planning algorithm. More specifically, let X denote the space of all admissible configurations of a mechanical system. A motion planner is given by a splitting X×X=F₁F₂F_k (where F₁,…,F_k are pairwise disjoint ENRs, see below) and by continuous maps s_j :F_j→PX, such that Es_j=1_Fj. Here PX denotes the space of all continuous paths in X (admissible motions of the system) and E :PX→X×X denotes the map which assigns to a path the pair of its initial–end points. Any motion planner determines an algorithm of motion planning for the system. In this paper we apply methods of algebraic topology to study the minimal number of sets F_j in any motion planner in X. We also introduce a new notion of order of instability of a motion planner; it describes the number of essentially distinct motions which may occur as a result of small perturbations of the input data. We find the minimal order of instability, which may have motion planners on a given configuration space X. We study a number of specific problems: motion of a rigid body in R³, a robot arm, motion in R³ in the presence of obstacles, and others.     

Brownian motion and algorithm complexity

The Brownian motion is shown to be a useful tool in analysing some sorting and tree manipulation algorithms.     

Covering location problem of emergency service facilities in an uncertain environment

In practical location problems on networks, the response time between any pair of vertices and the demands of vertices are usually indeterminate. This paper employs uncertainty theory to address the location problem of emergency service facilities under uncertainty. We first model the location set covering problem in an uncertain environment, which is called the uncertain location set covering model. Using the inverse uncertainty distribution, the uncertain location set covering model can be transformed into an equivalent deterministic location model. Based on this equivalence relation, the uncertain location set covering model can be solved. Second, the maximal covering location problem is investigated in an uncertain environment. This paper first studies the uncertainty distribution of the covered demand that is associated with the covering constraint confidence level α. In addition, we model the maximal covering location problem in an uncertain environment using different modelling ideas, namely, the (α, β)-maximal covering location model and the α-chance maximal covering location model. It is also proved that the (α, β)-maximal covering location model can be transformed into an equivalent deterministic location model, and then, it can be solved. We also point out that there exists an equivalence relation between the (α, β)-maximal covering location model and the α-chance maximal covering location model, which leads to a method for solving the α-chance maximal covering location model. Finally, the ideas of uncertain models are illustrated by a case study.     

Repair strategies in an uncertain environment: Markov decision process approach

This paper deals with repair strategies that maximize the time until a catastrophic event, that is, when there is a vital need for equipment, and the equipment fails to function. We examine the case where the need for the equipment varies over time according to a Markov chain. This means that the environment can be in different states, each with their own probability of the initiating event occurring. We model the form of the optimal policy for repair under this uncertain environment by Markov decision processes.     

Fuzzy linear programming with vague objective coefficients in an uncertain environment

In this paper, a new fuzzy linear programming (FLP)-based methodology using a specific membership function named modified logistic membership function is proposed. The modified logistic membership function is first formulated and its flexibility established by an analytical approach. This membership function is tested for its useful performance through an illustrative example by employing FLP. The developed methodology of FLP has provided confidence in applying to real-life industrial production planning problem. This approach of solving industrial production planning problem can provide feedback to the decision maker, implementer and analyst. In such cases, this approach can be called interactive FLP. There is a possibility to design the self-organizing of the fuzzy system for the product mix selection problem in order to find a satisfactory solution. The decision maker, analyst and implementer can incorporate their knowledge and experience to obtain the best outcome.     

The anticipative concept in warehouse optimization using simulation in an uncertain environment

The modern business environment is highly unpredictable. An anticipation approach in a real case study is presented to cope with such instability and minimize the total inventory cost without stock-outs occurring and inventory capacity being exceeded. The anticipation concept is performed using simulation models supported by inventory control algorithms on a selected sample of representative items. The inventory control algorithms include Silver–Meal, Part period balancing, Least-unit cost, and Fuzzy inventory control algorithm based on fuzzy stock-outs, highest inventory level and total cost. Transportation cost is explicitly defined as a discrete function of shipment size. The algorithms are tested on historic data. Simulation results are presented and the risk of accepting them as reliable is discussed. The process of simulation model implementation is briefly discussed to further validate the model and train order managers to use the simulation model in their order placement process.     

Aircraft control for flight in an uncertain environment: Takeoff in windshear

The design of the control of an aircraft encountering windshear after takeoff is treated as a problem of stabilizing the climb rate about a desired value of the climb rate. The resulting controller is a feedback one utilizing only climb rate information. Its robustness vis-a-vis windshear structure and intensity is illustrated via simulations employing four different windshear models.Notations ARL aircraft reference line - D drag force, lb - g gravitational force per unit mass=const, ft sec^–2 - h vertical coordinate of aircraft center of mass (altitude), ft - L lift force, lb - m aircraft mass=const, lb ft^–1 sec² - O mass center of aircraft - S reference surface, ft² - t time, sec - T thrust force, lb - V aircraft speed relative to wind-based reference frame, ft sec^–1 - V _e aircraft speed relative to ground, ft sec^–1 - W _x horizontal component of wind velocity, ft sec^–1 - W _h vertical component of wind velocity, ft sec^–1 - x horizontal coordinate of aircraft center of mass, ft - relative angle of attack, rad - relative path inclination, rad - _e path inclination, rad - thrust inclination, rad - air density=const, lb ft² sec² Dot denotes time derivative.     

The Analytic Hierarchy Process in an uncertain environment: A simulation approach

Traditionally, decision makers were forced to converge ambiguous judgments to a single point estimate in order to describe a pairwise relationship between alternatives relative to some criterion for use in the Analytic Hierarchy Process (AHP). Since many circumstances exist which make such a convergence difficult, confidence in the outcome of an ensuing AHP synthesis may be reduced. Likewise, when a group of decision makers cannot arrive at a consensus regarding a judgment, some members of the group may simply lose confidence in the overall synthesis if they lack faith in some of the judgments. The AHP utilizes point estimates in order to derive the relative weights of criteria, sub-criteria, and alternatives which govern a decision problem. However, when point estimates are difficult to determine, distributions describing feasible judgments may be more appropriate. Using simulation, we will demonstrate that levels of confidence can be developed, expected weights can be calculated and expected ranks can be determined. It will also be shown that the simulation approach is far more revealing than traditional sensitivity analysis.     

Optimal assignment of resources to strengthen the weakest link in an uncertain environment

The weakest link principle applies to many real-life situations where a system is as productive as its bottleneck. The purpose of this paper is to show how the efficiency of a manufacturing or service process (i.e., the strength of a chain) may be maximized by optimal allocation of resources to improve the performance of the bottleneck (i.e., strengthen the weakest link) in an uncertain environment. Specifically, we consider two different versions of the stochastic bottleneck assignment problem (SBAP), which is a variation of the classic assignment problem (AP), with respective goals of minimizing the expected longest processing time and maximizing the expected lowest production rate. It is proven that each of the two intrinsically difficult SBAPs is reducible to an efficiently solvable AP provided that the processing times or the production rates are independent random variables following some families of probability distributions.     

Linearized viscoelastic Oldroyd fluid motion in an almost periodic environment

In most of the linear homogenization problems involving convolution terms so far studied, the main tool used to derive the homogenized problem is the Laplace transform. Here we propose a direct approach enabling one to tackle both linear and nonlinear homogenization problems that involve convolution sequences without using Laplace transform. To illustrate this, we investigate in this paper the asymptotic behavior of the solutions of a Stokes–Volterra problem with rapidly oscillating coefficients describing the viscoelastic fluid flow in a fixed domain. Under the almost periodicity assumption on the coefficients of the problem, we prove that the sequence of solutions of our ?‐problem converges in L² to a solution of a rather classical Stokes system. One important fact is that the memory disappears in the limit. To achieve our goal, we use some very recent results about the sigma‐convergence of convolution sequences. Copyright © 2013 John Wiley & Sons, Ltd.     

A robust optimization model for multi-site production planning problem in an uncertain environment

This paper addresses the multi-site production planning problem for a multinational lingerie company in Hong Kong subject to production import/export quotas imposed by regulatory requirements of different nations, the use of manufacturing factories/locations with regard to customers’ preferences, as well as production capacity, workforce level, storage space and resource conditions at the factories. In this paper, a robust optimization model is developed to solve multi-site production planning problem with uncertainty data, in which the total costs consisting of production cost, labor cost, inventory cost, and workforce changing cost are minimized. By adjusting penalty parameters, production management can determine an optimal medium-term production strategy including the production loading plan and workforce level while considering different economic growth scenarios. The robustness and effectiveness of the developed model are demonstrated by numerical results. The trade-off between solution robustness and model robustness is also analyzed.     

Influence of vortex structures on the controlled motion of an above-water screwless robot

This paper is devoted to an experimental investigation of the motion of a rigid body set in motion by rotating two unbalanced internal masses. The results of experiments confirming the possibility of motion by this method are presented. The dependence of the parameters of motion on the rotational velocity of internal masses is analyzed. The velocity field of the fluid around the moving body is examined.     

Geometry of the motion of robot manipulators

A p-parametric robot is a mapping g of R^p into the homogeneous space P=C₆×C₆/Diag(C₆×C₆) given by the formula g(u₁,...,u_p=exp u₁X₁..... exp u_pX_p, where C₆, is the Lie group of all congruences of E₃ and X₁,..., X_p are fixed vectors from the Lie algebra of C₆. We characterize the set g(R^p) locally by a system of PDE and give some geometrical properties of g as a p-dimensional motion for p<6. We also characterize the Frenet frame of g and show how to construct it for the robot manipulator given by its axes X₁,...,X_p.     

不确定环境下多自主体系统的分布式估计与控制

多自主体系统是当前系统控制界研究的热点问题. 在实际中, 自主体系统通常并不是在理想的环境下执行任务, 而是面临多源头、多层次和多变化的各类不确定性因素的影响. 它们通过在微观层面上影响各自主体决策的正确性, 从而在宏观上对自主体系统的整体行为产生显著影响. 不确定性因素和多自主体系统分布式信息架构交互耦合, 给系统的设计与分析带来本质性困难. 本文围绕分布式估计与分布式控制问题, 研究在随机通信噪声、数据丢失、量化和系统未知结构参数等不确定因素影响下, 如何为各自主体设计更加鲁棒、更加有效的分布式估计算法及分布式控制律, 以实现全局估计与控制目标, 并对闭环系统性能进行系统分析.