Operations Research Transactions

Scheduling on single machine and identical machines with rejection

GAO Qiang, LU Xiwen

2014, 18(4): 1-10.

Asbtract ( 809 )

PDF (510KB) ( 1091 )

References | Related Articles | Metrics

We consider scheduling problems with rejection for both single machine and identical machines in this paper. For the single machine problems, each job has penalty \alpha times of its processing time. If jobs have release dates, the problem of minimizing the sum of makespan and total penalty can be solved in polynomial time. If all jobs arrive at time zero, the problem of minimizing the sum of total completion time and total penalty also can be solved in polynomial time. For the identical machines problems, jobs arrive over time at two different time points. The objective is to minimize the sum of makespan and total penalty. We design on-line approximation algorithms with competitive ratios 2 or 4-2/m for the two cases when the number of machines is two or m, respectively.

Self-concordant exponential kernel function based interior point algorithm for second-order cone optimization

ZHANG Jing, BAI Yanqin

2014, 18(4): 11-24.

Asbtract ( 887 )

PDF (591KB) ( 615 )

References | Related Articles | Metrics

This paper presents a primal-dual interior point algorithm for second-order cone optimization based on a new self-concordant (SC) exponential kernel function. By the special relationship between the second derivative and the third derivative of SC exponential kernel function, we use Newton direction to replace the negative gradient direction in solving the central path. Since the SC exponential kernel function does not satisfy the ``Eligible'' property, we use the technique of Newton method minimizing the unconstraint problem with SC object function in analyzing the complexity bound of algorithm. We estimate the decrease of proximity function which is defined by SC exponential kernel function during the inner iteration. We obtain the complexity bound for large-update methods, which is O(2N \frac{\log 2N}{\varepsilon}), where N is the number of the second-order cones. This result coincides with the complexity bound in the case of linear optimization. Finally, we give some numerical examples to show the efficiency of algorithm.

Local strategic interaction with heterogeneous link costs in the endogenous network

SUN Liping, GAO Hongwei, VASIN Alexander, SONG Li, LI Ru, WANG Lei

2014, 18(4): 25-35.

Asbtract ( 764 )

PDF (535KB) ( 570 )

References | Related Articles | Metrics

In the context of endogenous network formation, players can only play coordination game with their direct neighbors. In the network formation process, the cost of link formation is heterogeneous (with two levels), and players would bear high-level costs when establishing links with players who choose an efficient action, and would bear low-level costs when establishing links with players who choose a risk-dominated action. In the case of heterogeneous link costs, the paper firstly gives an explicit description of the nature of network structure and players' choices in the equilibrium outcomes, and has analytically studied how the cost of link formation affecting the equilibrium outcomes.

Satisfaction optimization transportation problem

HU Xunfeng, LI Dengfeng

2014, 18(4): 36-44.

Asbtract ( 806 )

PDF (589KB) ( 1167 )

References | Related Articles | Metrics

Traditional transportation problem only considers the efficiency of the distribution scheme rather than the members' satisfaction. After introducing the notion of member's satisfaction to the distribution scheme, this paper introduces the satisfaction optimization transportation problem, and proposes the satisfaction optimization transportation model aiming at maximizing the relative equalities among the members. Some further results are given, including: (1) If the feasible domain of the transportation problem is not empty, so does the solution set of the new model; (2) From the perspective of satisfaction, the model has a unique solution. Additionally, this paper gives a calculation method for the new model. Research results further enrich types of transportation problems, and can be taken as reference to solve other types of transportation problems.

Supply chain coordination contract with manufacturing cost screening and sales effort incentives

HUANG Meiping, WANG Xianyu, ZHANG Huan

2014, 18(4): 45-57.

Asbtract ( 755 )

PDF (967KB) ( 780 )

References | Related Articles | Metrics

To solve the low efficiency caused by hiding of the manufacturer's cost and retailer's efforts in a two-echelon supply chain, a virtual-third party was introduced as a selfless principal based on principal agent theory. Firstly, a supply chain coordination model under adverse selection and moral hazard was developed to screen the manufacturer's true cost and make retailer work hard. Secondly, the relationship among the coordination contract parameters was obtained. Finally, main results revealed that the coordination contract could incent the manufacturer to tell the truth, and the retailer cooperated with the low-cost manufacturers to carry out the optimal efforts. Furthermore, a numerical example was used to verify the conclusions.

Nonlinear scalarization characterizations for \varepsilon-properly efficient solutions in vector optimization

XIA Yuanmei, ZHAO Kequan

2014, 18(4): 58-64.

Asbtract ( 1045 )

PDF (435KB) ( 708 )

References | Related Articles | Metrics

In this paper, a nonlinear scalarization characterization of \varepsilon-properly efficient solutions is given by means of a kind of nonlinear scalarization function proposed by G\"{o}pfert et al. for vector optimization problems. And several examples are proposed to illustrate the main results.

The t/k-diagnosability and diagnosis algorithm of Pancake networks

SONG Sulin, LIN Limei, ZHOU Shuming

2014, 18(4): 65-77.

Asbtract ( 964 )

PDF (1434KB) ( 637 )

References | Related Articles | Metrics

Fault tolerance is especially important for multiprocessor system since the growing size of the multiprocessor system increases its vulnerability to component failures. The t/k-diagnosis is a kind of diagnostic strategy at system level that can significantly enhance the multiprocessor system's self-diagnosing capability. It can detect up to t faulty processors (or nodes, units) which might include at most k misdiagnosed processors. This paper first explores the fault tolerance of Pancake networks P_n (n\geq 5), and then proves that P_n is ((k+1)n-3k-1)/k-diagnosable under the PMC model, 1\leq k\leq 3 Finally it proposes a quick diagnosis algorithm with complexity O(NlogN) to identify all the faulty nodes.

Necessary and sufficient conditions for majority satisfaction preference rule

HU Yuda

2014, 18(4): 78-84.

Asbtract ( 765 )

PDF (487KB) ( 523 )

References | Related Articles | Metrics

This paper studies a basic mathematical theoretic problem of group decision making based on satisfaction choice. We prove that necessary and sufficient conditions for any group satisfaction preference mapping are majority satisfaction preference rule of the group on alternative set.

Minimal skew energies of oriented bicyclic graphs without even cycles

XIAO Mao, WANG Wenhuan

2014, 18(4): 85-95.

Asbtract ( 881 )

PDF (574KB) ( 695 )

References | Related Articles | Metrics

Let G be a simple connected graph. By assigning an orientation to each edge of G, we obtained an oriented graph G^{\sigma}. The skew energy E_{s}(G^{\sigma}) of an oriented graph G^\sigma is defined as the sum of the absolute eigenvalues of the skew adjacency matrix for G^\sigma. Let \mathcal{B}^\circ_{n} be the set of bicyclic graphs without even cycles having n vertices. The ordering of graphs in \mathcal{B}^\circ_{n} in terms of their minimal skew energies was considered. By employing the integral formula of skew energy and knowledge of real analysis, we deduced the first threegraphs with minimal skew energies in \mathcal{B}^\circ_{n} for n\geq 156 and 155 \geq n\geq 12, respectively.

The minimum cover flow problem in networks

LIN Hao, LIN Lan

2014, 18(4): 96-104.

Asbtract ( 790 )

PDF (795KB) ( 597 )

References | Related Articles | Metrics

The maximum flow problem and the minimum cost flow problem are two basic models in theory of network flows. In order to study the blocking phenomena, the minimum saturated flow problem has arisen in the literature, but it is NP-hard. This paper studies the minimum cover flow problem, that is, we look for a flow with minimum value such that the flow in each arc is not less than a prescribed amount. The main result is to establish a polynomial-time algorithm which can be applied to the minimum saturated flow problem.

Bandwidth sum with an edge added

LIN Yishu, LIU Yan

2014, 18(4): 105-110.

Asbtract ( 582 )

PDF (452KB) ( 567 )

References | Related Articles | Metrics

Suppose $f$ is a one-to-one mapping from $V(G)$ onto $\{1,2,\cdots,|V(G)|\}$. Let $BS(G,f)=\sum\limits_{uv\in E(G)}|f(u)-f(v)|$. The bandwidth sum of $G$, denoted by $BS(G)$, is $BS(G)=\min\limits_{f}BS(G,f)$. In this paper, we obtain the relationship between $BS(G+e)$ and $BS(G)$, where $e\in\overline{E(G)}$, $BS(G)+1\leq BS(G+e)\leq BS(G)+n-1$. We also show that these bounds are sharp.

The coordination of transportation and serial batching scheduling

GU Cunchang, ZHANG Yuzhong

2014, 18(4): 111-118.

Asbtract ( 810 )

PDF (546KB) ( 584 )

References | Related Articles | Metrics

The coordination of production scheduling and transportation has recently received a lot of attention in logistics and supply chain management. We study a coordinated scheduling problem in which the jobs are transported by $m$ vehicles from a holding area to a single serial batching machine for further processing, each batch of jobs to be processed occurs a processing cost. The objective is minimizing the sum of the jobs' total completion time and the total processing cost. Under the condition of the job processing times are equal, if the job assignment to the vehicles is predetermined, we provide a polynomial time dynamic programming algorithm, for the general problem, prove that it is {NP}-hard. When the returning time of vehicle is $0$, we present the approximation algorithm and prove that the worst case ratio of the algorithm is $2-\frac{1}{m}$.

A multiplier relaxation method for solving mathematical programs with complementarity constraints

LIU Shuixia, CHEN Guoqing

2014, 18(4): 119-130.

Asbtract ( 807 )

PDF (528KB) ( 725 )

References | Related Articles | Metrics

By using the Lagrange function of the complementarity problem, a new relaxed problem of MPCC is given. We show that the linear independence constraint qualification holds for the new relaxed problem under some mild conditions. Based on this, a multiplier relaxed method for solving MPCC is presented. The limited point of stationary points of the relaxed problems is M-stationary point under the MPCC-LICQ. Without requiring the second-order necessary condition, the limited point is B-stationary point if the ULSC holds. At last, we propose a new condition for convergence to B-stationary point.

Table of Content