Loading...

Table of Content

    30 December 2014, Volume 2 Issue 4
    Stochastic Optimization
    Policy Iteration Algorithms for Zero-Sum Stochastic Differential Games with Long-Run Average Payoff Criteria
    Jose Daniel Lopez-Barrientos
    2014, 2(4):  395.  doi:10.1007/s40305-014-0061-z
    Asbtract ( 568 )   PDF (433KB) ( 259 )  
    Related Articles | Metrics

    This paper studies the policy iteration algorithm (PIA) for zero-sum stochastic differential games with the basic long-run average criterion, as well as with its more selective version, the so-called bias criterion. The system is assumed to be a nondegenerate diffusion. We use Lyapunov-like stability conditions that ensure the existence and boundedness of the solution to certain Poisson equation. We also ensure the convergence of a sequence of such solutions, of the corresponding sequence of policies, and, ultimately, of the PIA.

    Continuous Optimization
    Nesterov’s Smoothing and Excessive Gap Methods for an Optimization Problem in VLSI Placement
    Jian-Li Chen · Yan Cui · Wen-Xing Zhu
    2014, 2(4):  423.  doi:10.1007/s40305-014-0065-8
    Asbtract ( 286 )   PDF  
    Related Articles | Metrics

    In this paper, we propose an algorithm for a nonsmooth convex optimization problem arising in very large-scale integrated circuit placement. The objective function is the sum of a large number of Half-Perimeter Wire Length (HPWL) functions and a strongly convex function. The algorithm is based on Nesterov’s smoothing and excessive gap techniques. The main advantage of the algorithm is that it can capture the HPWL information in the process of optimization, and every subproblem has an explicit solution in the process of optimization. The convergence rate of the algorithm is O(1/k2); where k is the iteration counter, which is optimal. We also present preliminary experiments on nine placement contest benchmarks. Numerical examples confirm the theoretical results.

    Discrete Optimization
    Online Over Time Scheduling on Parallel-Batch Machines: A Survey
    Ji Tian · Ruyan Fu · Jinjiang Yuan
    2014, 2(4):  445.  doi:10.1007/s40305-014-0060-0
    Asbtract ( 260 )   PDF  
    Related Articles | Metrics

    Online scheduling is a rapidly developed branch in scheduling theory. In this paper, we present an extensive survey for online over time scheduling on parallel-batch machines. Some open problems are proposed for further research.

    Stochastic Optimization
    A Stochastic Inventory System with Postponed Demands and Infinite Pool in Discrete-Time Setup
    Velusamy Radhamani · P. Chitra Devi · Balasubramanian Sivakumar
    2014, 2(4):  455.  doi:10.1007/s40305-014-0063-x
    Asbtract ( 292 )   PDF  
    Related Articles | Metrics

    In this article, we consider a discrete-time inventory model in which demands arrive according to a discrete Markovian arrival process. The inventory is replenished according to an ðs; SÞ policy, and the lead time is assumed to follow a discrete phase-type distribution. The demands that occur during stock-out periods either enter a pool which has an infinite capacity or leave the system with a predefined probability. The demands in the pool are selected one by one, if the on-hand inventory level is above s þ 1; and the interval time between any two successive selections is assumed to have a discrete phase-type distribution. The joint probability distribution of the number of customers in the pool and the inventory level is obtained in the steady-state case.We derive the system performance measures under steady state and using these measures, the total expected cost rate of the system is calculated. The impacts of arrival rate on the performance measures are graphically illustrated. Finally, we study the impact of cost on the optimal values of the total expected cost rate, inventory level and the reorder point.

    Continuous Optimization
    Stochastic Nash Games for Markov Jump Linear Systems with State- and Control-Dependent Noise
    Huai-Nian Zhu · Cheng-Ke Zhang · Ning Bin
    2014, 2(4):  481.  doi:10.1007/s40305-014-0064-9
    Asbtract ( 283 )   PDF  
    Related Articles | Metrics

    This paper investigates Nash games for a class of linear stochastic systems governed by Itoˆ’s differential equation with Markovian jump parameters both in finite-time horizon and infinite-time horizon. First, stochastic Nash games are formulated by applying the results of indefinite stochastic linear quadratic (LQ) control problems. Second, in order to obtain Nash equilibrium strategies, crosscoupled stochastic Riccati differential (algebraic) equations (CSRDEs and CSRAEs) are derived. Moreover, in order to demonstrate the validity of the obtained results, stochastic H2/H control with state- and control-dependent noise is discussed as an immediate application. Finally, a numerical example is provided.

    Discrete Optimization
    Scheduling a Bounded Parallel-Batching Machine with Incompatible Job Families and Rejection
    Shi-Sheng Li · Ren-Xia Chen
    2014, 2(4):  499.  doi:10.1007/s40305-014-0062-y
    Asbtract ( 386 )   PDF  
    Related Articles | Metrics

    We study a scheduling problem with incompatible job families and rejection on a parallel-batching machine, where the objective is to minimize the makespan of all accepted jobs plus the total penalty of all rejected jobs. We provide a polynomial-time algorithm for the case where all jobs have identical release dates and a pseudo-polynomial-time algorithm for the case where the number of distinct elease dates is fixed. We also present a 2-approximation algorithm and a polynomial-time approximation scheme for the general problem.

    Continuous Optimization
    A Smoothing Method for Solving Bilevel Multiobjective Programming Problems
    Yi-Bing LV · Zhong-Ping Wan
    2014, 2(4):  511.  doi:10.1007/s40305-014-0059-6
    Asbtract ( 309 )   PDF  
    Related Articles | Metrics

    In this paper, a bilevel multiobjective programming problem, where the lower level is a convex parameter multiobjective program, is concerned. Using the KKT optimality conditions of the lower level problem, this kind of problem is transformed into an equivalent one-level nonsmooth multiobjective optimization problem. Then, a sequence of smooth multiobjective problems that progressively approximate the nonsmooth multiobjective problem is introduced. It is shown that the Pareto optimal solutions (stationary points) of the approximate problems converge to a Pareto optimal solution (stationary point) of the original bilevel multiobjective programming problem. Numerical results showing the viability of the smoothing approach are reported.