Loading...

Table of Content

    15 December 2016, Volume 20 Issue 4
     Stability of solutions to parametric optimization problems under bounded rationality
    YANG Guanghui, YANG Hui, XIANG Shuwen
    2016, 20(4):  1-10.  doi:10.15960/j.cnki.issn.1007-6093.2016.04.001
    Asbtract ( 789 )   PDF (536KB) ( 534 )  
    References | Related Articles | Metrics

     Parametric optimization has been widely applied in game theory, control theory, economics and management, engineering technology, etc. Recently, the stability of solutions to parametric optimization has attracted increasing attention. This paper mainly studies the stability of solutions to parametric optimization problems under bounded rationality. By introducing an abstract rationality function, two rational models M are established with two types of perturbations: the perturbation of both objective functions and feasible sets, and the perturbation of objective functions, feasible sets and parameters simultaneously. For the two perturbations above, by the ``generic'' method, the rational model M is structurally stable and is robust to \varepsilon-equilibria (or solutions), respectively. That is, the solutions to most of parametric optimization problems are stable in the sense of Baire category. Finally, an example is illustrated.

    An algorithm for elastic l_2-l_q regularization
    ZHANG Yong, YE Wanzhou
    2016, 20(4):  11-20.  doi:10.15960/j.cnki.issn.1007-6093.2016.04.002
    Asbtract ( 1220 )   PDF (872KB) ( 454 )  
    References | Related Articles | Metrics

    In this paper, we present an iteratively re-weighted l_{1} minimization (IRL1) algorithm for solving elastic l_{2}-l_{q} regularization. We prove that any sequence generated by the IRL1 algorithm is bounded and asymptotically regular. We further prove that the sequence is convergent based on an algebraic method for any rational q \in (0,1) and the limit is a stationary point of the elastic l_{2}-l_{q}(0<q<1) minimization problem. Numerical experiments on sparse signal recovery are presented to demonstrate the effectiveness of the proposed algorithm.

    A kind of cone-convexity for set-valued maps and its scalarization
    LI Fei, TANG Liping, YANG Xinmin
    2016, 20(4):  21-29.  doi:10.15960/j.cnki.issn.1007-6093.2015.04.003
    Asbtract ( 1327 )   PDF (472KB) ( 511 )  
    References | Related Articles | Metrics

    In this paper, we firstly introduce the notion of scalar cone-quasiconvexity for set-valued maps and discuss the relationships among several cone-convexities. A characterization for proper cone-quasiconvexity of set-valued maps is also given in the sense of a type of level set. Meanwhile, the composition rule of cone-convexity of set-valued maps is established by scalar increasing convex functions. We obtain a characterization for cone-quasiconvexity of set-valued maps by Gerstewitz functional finally.

    Two-stage supply chain scheduling with an assignable common due window
    ZHANG Yuzhong, ZHANG Long
    2016, 20(4):  30-38.  doi:10.15960/j.cnki.issn.1007-6093.2016.04.004
    Asbtract ( 1005 )   PDF (526KB) ( 495 )  
    References | Related Articles | Metrics

    This paper mainly addresses a two-stage supply chain scheduling problem in which jobs have an assignable common due window. The due window need to be determined, because the start and completion time of the window is a variable instead of a constant. A job which is processed completely by the machine need to be dispatched with batch to customer by many vehicles, and a job will incur a holding cost if its completion time is earlier than its dispatch date. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. The objective is to find the optimal size and location of the window, the optimal dispatch date for each job, as well as an optimal job sequence to minimize a cost function based on earliness, tardiness, holding time, window location, window size, and batch delivery. We consider the case where the unit cost of tardiness is not more than the unit cost of holding time, and the unit cost of holding time is not more than the unit cost of earliness. We provide an O(n^{8}) dynamic programming algorithm for this case.

    Defined contribution pension fund scheme with HARA preference under inflation risk
    CHANG Hao, WANG Chunfeng, FANG Zhenming
    2016, 20(4):  39-51.  doi:10.15960/j.cnki.issn.1007-6093.2016.04.005
    Asbtract ( 954 )   PDF (609KB) ( 333 )  
    References | Related Articles | Metrics

    Inflation risk is one of the most direct and important influential factors in the process of pension fund scheme management. In this paper, inflation risk is supposed to be measured by price index satisfying geometric Brownian motion. And instantaneous expected inflation rate is assumed to be driven by Ornstein-Uhlenbeck process. The fund manager plans to invest his real wealth in the financial market composed of multiple risky assets and expect to maximize expected utility of terminal real wealth. His goal is to obtain the optimal investment strategy for defined contribution pension fund scheme in the accumulation phase. Hyperbolic absolute risk aversion (HARA) utility function is of general utility framework and consists of power utility, exponential utility and logarithmic utility as specific cases. This paper supposes the risky aversion degree of fund manager to satisfy HARA utility and uses stochastic dynamic programming principle along with Legendre transform-dual theory to successfully obtain the closed-form expression of the optimal investment strategy. In addition, some special cases are derived in detail.

    A class recourse  stochastic programs algorithm with MaxEMin evaluation
    ZHANG Yanli, MA Xinshun
    2016, 20(4):  52-60.  doi:10.15960/j.cnki.issn.1007-6093.2016.04.006
    Asbtract ( 1021 )   PDF (564KB) ( 533 )  
    References | Related Articles | Metrics

    The recourse-based stochastic programming generally assumes that the probability distribution of the random variables has complete information, but the actual situation is that we often get only part of the information. In this paper, we establish a two-stage stochastic programming model with MaxEMin evaluation under linear partial information of discrete probability distribution. We use quadratic programming and the dual decomposition method to get the feasible and optimal cuttings, then give an algorithm based on the L-shaped method. Finally, a numerical example shows the effectiveness of the proposed algorithm.

    Scheduling with simple deterioration and past-sequence-dependent delivery times
    MIAO Cuixia, ZOU Juan
    2016, 20(4):  61-68.  doi:10.15960/j.cnki.issn.1007-6093.2016.04.007
    Asbtract ( 667 )   PDF (536KB) ( 418 )  
    References | Related Articles | Metrics

    In this paper, the single-machine scheduling problem with simple deterioration and past-sequence-dependent (p-s-d) job delivery times is considered, in which the processing time of each job is a simple linear increasing function of its starting time. When the machine can process only one job at a time, firstly, the makespan, the total (weighted) completion time and the total lateness minimization problems are solvable in polynomial, the EDD rule is not an optimal solution to the maximum lateness minimization problem, and an optimal solution to the case where jobs have agreeable due dates and deteriorating rates is proposed. When the machine can process up to $b$ jobs simultaneously as a batch, i.e., the parallel-batch scheduling problems, two polynomial time optimal algorithms for the makespan minimization problem and the total weighted completion time minimization problem are presented, respectively.

    Supply chain scheduling problem under simple linear deterioration on a single-machine with an unavailability constraint
    FAN Jing, LU Xiwen
    2016, 20(4):  69-76.  doi:10.15960/j.cnki.issn.1007-6093.2016.04.008
    Asbtract ( 930 )   PDF (527KB) ( 500 )  
    References | Related Articles | Metrics

    We study a single-machine supply chain scheduling problem with one unavailability constraint, in which the actual processing time of a job depends on the deteriorating operator and the beginning time of processing and the interrupted job is non-resumable. The sufficient available vehicles without capacity limit deliver batches of completed jobs to the customer. And the completed jobs before the unavailability interval must be delivered before or by the start time of the unavailability interval. The objective is to minimize the sum of total delivery time and total delivery cost. We show that the problem is NP-hard, and present a pseudo-polynomial-time dynamic programming. Moreover, we achieve a full polynomial time approximation scheme (FPTAS) based on the lower bound and the upper bound of the objective function value of the problem.

    Skew Randi\'{c} energy of an oriented graph
    GUO Lifeng, WANG Ligong
    2016, 20(4):  77-84.  doi:10.15960/j.cnki.issn.1007-6093.2016.04.009
    Asbtract ( 920 )   PDF (505KB) ( 358 )  
    References | Related Articles | Metrics

    Let G be a simple undirected graph and G^\sigma the corresponding oriented graph of G with the orientation \sigma. G is said to be the underlying graph of G^\sigma. The skew Randi\'{c} matrix of an oriented graph G^\sigma is the real symmetric matrix R_{s}(G^\sigma)=[(r_s)_{ij}], where
    (r_s)_{ij}=(d_id_j)^{-\frac{1}{2}} and (r_s)_{ji}=-(d_id_j)^{-\frac{1}{2}} if (v_i, v_j) is an arc of \sigma, otherwise (r_s)_{ij}=(r_s)_{ji}=0. The skew Randi\'{c} energy RE_s(G^\sigma) of G^\sigma is the sum of absolute values of the eigenvalues of R_{s}(G^\sigma). In this paper, we firstly
    characterize the coefficients of the characteristic polynomial of R_{s}(G^\sigma). Secondly we give an integral representation for the skew Randi\'{c} energy of G^\sigma. Thirdly we show a new upper bound of RE_s(G^\sigma). Finally we compute RE_s(G^\sigma) of oriented cycles.

    Convergence of nonmonotonic Perry-Shanno's memoryless quasi-Newton method with parameters
    HANG Dan, YAN Shijian
    2016, 20(4):  85-92.  doi:10.15960/j.cnki.issn.1007-6093.2016.04.010
    Asbtract ( 979 )   PDF (526KB) ( 354 )  
    References | Related Articles | Metrics

    A nonmonotonic Perry-Shanno's memoryless Quasi-Newton method with parameters for unconstrained optimization is investigated.The global convergence of
    this algorithm is proved for convex objective function when  parameters are in the given range.

    A no-wait flowshop scheduling problem with processing flexibility and transportation
    ZHONG Weiya, MA Xiaoru
    2016, 20(4):  93-101.  doi:10.15960/j.cnki.issn.1007-6093.2016.04.011
    Asbtract ( 732 )   PDF (770KB) ( 415 )  
    References | Related Articles | Metrics

    This paper addresses the performance of scheduling algorithms for a two-stage no-wait flowshop scheduling problem with processing flexibility and transportation, where each stage has one machine. Each job, composed of two operations, must be processed through the two stages without waiting time. We propose two approximation algorithms. The first algorithm is list scheduling and the second schedules the jobs in non-decreasing order of the total processing time of each job's two operations. We show that the worst case ratio of the algorithms is no more than 5/2 and 2, respectively. At last, we conduct numerical experiments to compare the performance of the algorithms. For the cases with different value of the parameters, we generate several instances. For every instance, the ratio of the algorithm's objective value and the optimal solution's objective value is obtained. For each case, the maximum, minimum and average value of the instances' ratio are obtained to analyze the performance of the two algorithms.

    Searching for two counterfeit coins
    WU Xiaohui, LI Shengjia
    2016, 20(4):  102-108.  doi:10.15960/j.cnki.issn.1007-6093.2016.04.012
    Asbtract ( 758 )   PDF (1777KB) ( 620 )  
    References | Related Articles | Metrics

    The following weighting problem is considered: determine two counterfeit coins which are heavier than good coins in a set of n coins of the same appearance using only an equal arms balance. Let L^{(2)}(n) denote the minimum number of weighings necessary when exactly two of n coins are known to be  defective. For all n\geq 2, it satisfies \lceil \log_3\binom{n}{2}\rceil \leq L^{(2)}(n)\leq\lceil \log_3\binom{n}{2}\rceil+1. It was conjectured that the lower bound is always achieved. In this paper, using an novel algorithm, we improve on the range of n for which the lower bound is reached.

    Approximation algorithms for two-machine flow shop scheduling with an outsourcing option
    CHEN Guangting, CHEN Lei, ZHANG An, CHEN Yong
    2016, 20(4):  109-114.  doi:10.15960/j.cnki.issn.1007-6093.2016.04.013
    Asbtract ( 783 )   PDF (517KB) ( 409 )  
    References | Related Articles | Metrics

    The paper investigates flow shop scheduling with an outsourcing option. The objective is to minimize the sum of the in-house cost and the outsourcing cost, where the in-house cost is measured by the maximum completion time of jobs. We design approximation algorithms to solve the problem. For two-machine flow shop, we provide an algorithm with a worst case ratio of 2. For two-machine ordered flow shop, we give an improved algorithm with worst case ratio \frac{3}{2}. Both ratios are tight.

    On the crossing numbers of join of the special graph on six vertices with nK_1, P_n or C_n
    ZHOU Zhidong, LI Long
    2016, 20(4):  115-126.  doi:10.15960/j.cnki.issn.1007-6093.2016.04.014
    Asbtract ( 782 )   PDF (1127KB) ( 326 )  
    References | Related Articles | Metrics

    The crossing numbers of a graph is a vital parameter and a hard problem in the forefront of topological graph theory.  Determining the crossing number of an arbitrary graphs is NP-complete problem. Because of its difficultly, the classes of graphs whose crossing number have been determined are very scarce. In this paper, for the special graph Q on six vertices, we through the disk drawing method to prove that the crossing numbers of its join with n isolated vertices as well as with the path P_{n} and with the cycle C_{n} are cr(Q+nK_{1})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor, cr(Q+P_{n})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor+1 and cr(Q+C_{n})=Z(6,n)+2\lfloor\frac{n}{2}\rfloor+3, respectively.