Table of Content

15 June 2015, Volume 19 Issue 2

Previous Issue    Next Issue

 Approximation algorithms for the  priority facility location problem with submodular penalties

WANG Ying, WANG Fengmin, XU Dachuan, XU Wenqing

2015, 19(2):  1-14.  doi:10.15960/j.cnki.issn.1007-6093.2015.02.001

Asbtract ( 1087 )   PDF (647KB) ( 1737 )  

References | Related Articles | Metrics

In this paper, we study priority facility location problem with submodular penalties where each client has a level-of-service requirement. An open facility must satisfy the requirement of the clients served by it, and there is a submodular penalty cost corresponding with the unserved clients. The objective is to minimize the sum of the opening cost, the connection cost and the submodular penalty cost. We present the integer program, the linear programming relaxation and the dual program for the problem. Using the primal-dual and greedy augmentation techniques, we then propose two approximation algorithms and obtain the approximation ratios of 3 and 2.375 respectively.

Necessary global optimality conditions and optimization methods for cubic polynomial optimization problems with linear constraints

YE Min, WU Zhiyou, ZHANG Liang

2015, 19(2):  15-28.  doi:10.15960/j.cnki.issn.1007-6093.2015.02.002

Asbtract ( 1341 )   PDF (592KB) ( 1410 )  

References | Related Articles | Metrics

In this paper, the global optimality conditions and optimization methods for cubic polynomial optimization problems with linear inequality  constraints are considered. Firstly,  we propose a necessary global optimality condition for cubic polynomial optimization problems with linear inequality constraints. Then, a new local optimization method (or called  strongly local optimization methods) is presented by using its necessary global optimality conditions. A global optimization method is proposed for cubic polynomial optimization problems with linear inequality constraints by combining the new local optimization methods together with some auxiliary functions. Finally, some numerical examples are given to illustrate that these approaches are efficient.

A global optimization method for solving the linear semivectorial bilevel programming problem

LV Yibing, WAN Zhongping

2015, 19(2):  29-36.  doi:10.15960/j.cnki.issn.1007-6093.2015.02.003

Asbtract ( 968 )   PDF (556KB) ( 1410 )  

References | Related Articles | Metrics

In this paper, we are concerned with global optimization approach for solving the linear semivectorial bilevel programming (LSBP) problem. Using the duality gap of the lower level programs, we construct the corresponding penalized problem. By analyzing the relationships between the optimal solutions of the original problem and the vertices of the feasible region of the penalized problem, we transform the LSBP problem to a series of linear programming problems. Then, the global optimal solution of the LSBP problem can be obtained by solving a series of linear programming problems. The numerical results show that the algorithm proposed is feasible to the LSBP problem.

A review of re-entrant scheduling problems

JING Caixia, ZHAO Congli, YUAN Erming

2015, 19(2):  37-44.  doi:10.15960/j.cnki.issn.1007-6093.2015.02.004

Asbtract ( 1056 )   PDF (1205KB) ( 1349 )  

References | Related Articles | Metrics

In contrast to the classical scheduling assumption that each job visits each machine once at most, jobs with reentrant style are of a new type of scheduling problems. The basic characteristic of a re-entrant problem is that a job visits certain machines more than once. Re-entrance is usually found in semiconductor manufacturing, and also many other fields. Recently many papers have dealt with the re-entrant scheduling problems. Results and contributions of these references are presented and analyzed in this paper. The contents and methods are classified and introduced according to the machine environments, including single machine, flow shop, flexible flow shop and others. Research directions and trends of re-entrant scheduling problems in the future are presented  at last.

The Harary index of tricyclic graphs

CAI Gaixiang, XING Baohua, YU Guidong

2015, 19(2):  45-53.  doi:10.15960/j.cnki.issn.1007-6093.2015.02.005

Asbtract ( 1193 )   PDF (1318KB) ( 1337 )  

References | Related Articles | Metrics

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a  graph. Tricyclic graphs are  connected graphs in which the number of edges equals the number of vertices plus two. In this paper, we determine graphs with the largest Harary index among all the tricyclic graphs, and we also give graphs with the second largest Harary index among all the tricyclic graphs with three cycles.

Two results for single-machine two-agent scheduling problems

WAN Long

2015, 19(2):  54-60.  doi:10.15960/j.cnki.issn.1007-6093.2015.02.006

Asbtract ( 931 )   PDF (475KB) ( 1268 )  

References | Related Articles | Metrics

The paper considers two two-agent scheduling problems on a single machine. For the first two-agent scheduling problem, the objective of agent A is to minimize the total weighted completion time of all jobs of agent A while the objective of agent B is to minimize the maximum cost of the jobs of agent B. For the second two-agent scheduling problem, the objective of agent A is to minimize the total completion time of all jobs of agent A while the objective of agent B is to minimize the makespan which is defined as the maximum completion time of all the jobs of agent B. In this paper, we prove that the first problem is NP-hard in the strong sense which improves the current complexity result and design a dynamic programming other than the previous known algorithm for the second problem.

Properties and solving method of  tau-value for fuzzy cooperative games with multilinear extension form

YANG Dianqing, LI Dengfeng

2015, 19(2):  61-71.  doi:10.15960/j.cnki.issn.1007-6093.2015.02.007

Asbtract ( 1002 )   PDF (562KB) ( 1263 )  

References | Related Articles | Metrics

In this paper, we research the solving method and properties of  tau-value for fuzzy cooperative games. Using the multilinear extensive method, we define the tau-value for fuzzy cooperative games, prove its existence, uniqueness and other properties, and deduce the computational formulae of the  tau-value for convex fuzzy cooperative games. The research result shows that the  tau-value for the fuzzy cooperative games with multilinear extension form is an extension of the  tau-value for crisp cooperative games. Especially, for the convex fuzzy cooperative games, the computational process of the  tau-value can be simplified.

A scheduling strategy for dynamic vehicle routing problem based on double chains coding

NING Tao, CHEN Rong, GUO Chen, LIANG Xu

2015, 19(2):  72-82.  doi:10.15960/j.cnki.issn.1007-6093.2015.02.008

Asbtract ( 835 )   PDF (2109KB) ( 1298 )  

References | Related Articles | Metrics

For the purpose of solving the scheduling of dynamic vehicle routing problem, this paper establishes the simulation model to minimize the cost and stability value and maximize the freight rate, and an improved hybrid multi-phases quantum particle swarm algorithm was proposed. Firstly, it proposes the method of double chains structure coding including vehicle allocation chain and goods chain. Secondly, it proposes a dynamic scheduling strategy based on period-driven and event-driven. Finally, a novel method is applied to a dynamic simulation and the result of comparing with other classical algorithms verifies its effectiveness.

Global optimality conditions for non-convex cubic minimization problem with binary constraints

ZHANG Liang,WANG Yan,LI Guoquan

2015, 19(2):  83-90.  doi:10.15960/j.cnki.issn.1007-6093.2015.02.009

Asbtract ( 767 )   PDF (475KB) ( 1198 )  

References | Related Articles | Metrics

In this paper, we consider a special non-convex cubic optimization problem with binary constraints, and present a global optimal necessary and sufficient condition for this special non-convex cubic optimization problem. The results of this paper extend some corresponding results on global optimality conditions in some references in present information. Numerical examples show that the global optimal necessary and sufficient condition can effectively determine the optimal solution for the non-convex cubic optimization problem.

Upper bounds of the arc-chromatic number of tournaments

XU Chuandong,ZHANG Shenggui,WANG Yi

2015, 19(2):  91-98.  doi:10.15960/j.cnki.issn.1007-6093.2015.02.010

Asbtract ( 757 )   PDF (1610KB) ( 1129 )  

References | Related Articles | Metrics

The arc-chromatic number of a digraph is the smallest number of colors required in an arc-coloring such that no two consecutive arcs get the same color. We first introduce some results on the arc-coloring of digraphs, then give a discussion about the upper bound of the arc-chromatic number of tournaments. By determining the maximum arc-chromatic number of tournaments with order at most $8$, we show that although the upper bound of the arc-chromatic number of general digraphs is tight, it is not tight for tournaments.

The maximum signless Laplacian separator of unicyclic and bicyclic graphs

JIAN Xiangguo,YUAN Xiying,ZHANG Man

2015, 19(2):  99-104.  doi:10.15960/j.cnki.issn.1007-6093.2015.02.011

Asbtract ( 917 )   PDF (799KB) ( 1206 )  

References | Related Articles | Metrics

Let G be a graph of order n and q_{1}(G)\geq q_{2}(G)\geq \cdots \geq q_{n}(G) be its Q-eigenvalues. The signless Laplacian separator  S_{Q}(G) of G is defined as S_{Q}(G)=q_{1}(G)-q_{2}(G). In this paper, we study the maximum signless Laplacian separator of unicyclic and bicyclic graphs and characterize the extremal graphs, respectively.

A characterization of weakly (C,\varepsilon)-efficient solution of vector optimization via nonlinear scalarization

GUO Hui

2015, 19(2):  105-110.  doi:10.15960/j.cnki.issn.1007-6093.2015.02.012

Asbtract ( 831 )   PDF (430KB) ( 1216 )  

References | Related Articles | Metrics

Recently, Guti\'{e}rrez et al. proposed a new type of efficiency based on co-radiant set which called (C,\varepsilon)-efficient solution in vector optimization. This new notion of efficiency unifies some well-known concepts introduced previously in the literature. In this paper, we characterizes the new (C,\varepsilon)-efficient solution by a nonlinear scalarization function proposed by G\"{o}pfert, et al. Furthermore, an example is given to illustrate our main result.

Capacitated house market model with tenant under weak preferences

WU Weirang,CHEN Jinyang,WENG Yalan

2015, 19(2):  111-126.  doi:10.15960/j.cnki.issn.1007-6093.2015.02.013

Asbtract ( 507 )   PDF (2042KB) ( 1474 )  

References | Related Articles | Metrics

In this paper, the capacitated house market model with tenant under weak preferences problem has been considered. According to this model, we propose a kind of algorithm mechanism which is the extension of TTC algorithm, known as the Remove Selection algorithm(called CTTC) mechanism. In addition, we show that this kind of mechanism by using CTTC of the model satisfies individual rationality, Pareto-efficient and strategy-proof, and the complexity of CTTC algorithm is O(n_{1}^{2}(n_{1}n_{2}+n_{2}^{2})), where n_{1} is the number of agents, n_{2} is the number of the house.