Operations Research Transactions

Optimization in many-to-one two-sided matching market

LI Jianrong

2013, 17(4): 1-10.

Asbtract ( 1600 )

PDF (550KB) ( 2041 )

References | Related Articles | Metrics

The game-theoretic solutions defined in two-sided market allow the interests of agents on the same side of the market to be simultaneously maximized. The theoretic basis of such kind of optimization is the stability of the selection matching. This paper uses game-theoretic method to study the optimization in many-to-one two-sided matching market. Under the presence of substitutable and LAD(Law of Aggregate Demand) preferences, we prove that the selections made by firms produce a stable matching, so do the selections made by workers.

Time inconsistency of the mean-variance optimal policy in stochastic markets and its revision

LI Gang, CHEN Zhiping

2013, 17(4): 11-23.

Asbtract ( 1484 )

PDF (550KB) ( 675 )

References | Related Articles | Metrics

Due to the non-separability of the variance operator in sense of dynamic programming, the optimal investment policy of the multi-period mean-variance model in stochastic markets doesn't satisfy the time consistency corresponding to Bellman's optimality principle. To overcome this shortcoming, we first propose a new time consistency in stochastic markets, which is weaker than Bellman's optimality principle, and prove that the optimal investment policy satisfies the weak time consistency at any intermediate period as long as the investor's wealth is no more than a specific threshold. When the investor's wealth exceeds the given threshold, the weak time consistency no longer holds, and the investor becomes irrational since he minimizes mean and variance of the terminal wealth at the same time. To avoid this, by relaxing the self-financing constraint, we revise the optimal investment policy so that the revised policy can make the investor rational and can attain the same mean and variance of the terminal wealth as those of the optimal investment policy. It is shown that, in this process, a positive cash flow should be taken out of the market. These conclusions show that the revised policy is more efficient than the optimal investment policy. Our results extend existing conclusions for the multi-period mean-variance model in deterministic markets and the understanding about time consistency.

Approximating viability kernel for control systems

CHEN Zheng, GAO Yan

2013, 17(4): 24-32.

Asbtract ( 991 )

PDF (840KB) ( 589 )

References | Related Articles | Metrics

The computation of the viability kernel is an important topic in control theory community. In this paper, we propose a new algorithm that computes the viability kernel of a discrete-time system. Based on the theory of machine learning, the algorithm of approximating viability kernel is presented. We give some conditions that guarantee the convergence of the approximations towards the actual viable kernel. This method avoids the exponential growth of the computing time with the dimension of the control space. Finally, examples are given to illustrate this result.

Optimization of shock model being maintained under imperfect inspection

LI Ling, CHENG Guoqing

2013, 17(4): 33-42.

Asbtract ( 1010 )

PDF (719KB) ( 529 )

References | Related Articles | Metrics

In view of imperfect inspections in manufacturing systems, a shock model with imperfect inspection is considered. The system is periodically inspected so that a preventive maintenance can be performed when necessary. Assume that the system is deteriorating and has k failure types. An explicit expression of average cost rate C(T,N) of system is given by using renewal process and considering inspection cycle T and replacement policy N. A numerical algorithm is given to obtain the optimal joint strategy. Finally, it provides a numerical example to illustrate the proposed model, and also studies the impact of inspection level on average cost rate.

Extended Viterbi algorithm based on dynamic programming for high-order hidden Markov model

YE Fei, WANG Yifei

2013, 17(4): 43-55.

Asbtract ( 1555 )

PDF (696KB) ( 708 )

References | Related Articles | Metrics

Firstly, high-order hidden Markov model is transformed into an equivalent first-order vector-valued hidden Markov model by using Hadar's equivalent transformation method. Secondly, the Viterbi algorithm for the first-order vector-valued hidden Markov model is established according to the dynamic programming principle. Finally, the extended Viterbi algorithm based on dynamic programming for high-order hidden Markov model is established by using the equivalence relation between high-order hidden Markov and the first-order vector-valued hidden Markov model. This study extends the related Viterbi algorithms discussed in almost all literatures of hidden Markov model, and then contributes to the algorithmic theory of high-order hidden Markov model.

Minimize total lateness with deteriorating jobs based on rescheduling problem

XU Xiaoyan, MU Yundong, HAO Yun

2013, 17(4): 56-62.

Asbtract ( 1061 )

PDF (590KB) ( 662 )

References | Related Articles | Metrics

In this paper, we consider two single machine rescheduling problems with deteriorating jobs under sequence disruptions, the actual processing time of a job is a linear function of the starting time for deteriorating job. Rescheduling means that a set of original jobs has already been scheduled to minimize some classical objective, then a new set of jobs arrives and creates a disruption. We consider the rescheduling problem to minimize the total lateness under a limit of the sequence disruption for deteriorating job. We research the properties of feasible schedules and optimal schedules for two problems, the jobs in the set of original jobs or new jobs are ordered by non-decreasing order of the processing rate alpha_j. For each problem, the polynomial algorithm is proposed by sorting by stages or dynamic programming method, respectively.

Preemptive online algorithms for scheduling on three machines with hierarchies

YAO Ran, CHEN Guangting, ZHANG An, CHEN Yong

2013, 17(4): 63-68.

Asbtract ( 1118 )

PDF (694KB) ( 563 )

References | Related Articles | Metrics

We consider online scheduling on three machines with hierarchies. Each job, as well as each machine, has a hierarchy of either 1 or 2 associated with it. A job can be scheduled on a machine only when its hierarchy is no smaller than that of the machine. Preemption is allowed. The objective is to minimize the maximum completion time of jobs. If there are two machines of hierarchy 1, then we give an online algorithm with competitive ratio 3/2 and prove that it is best possible. If only one machine has a hierarchy of 1, then a 3/2-competitive algorithm is also provided.

An extended p-median problem with investment constraint and uncertain p

JIANG Jianlin, LI Xue, ASSANI Saeed, WU Pu, WANG Cancan

2013, 17(4): 69-79.

Asbtract ( 1320 )

PDF (820KB) ( 642 )

References | Related Articles | Metrics

p-median problem is a classical model in facility location and it has vast applications in related areas such as transportation and logistics. An extended p-median problem is investigated in this paper, in which the number of facilities to be located is uncertain and an investment constraint is considered. This makes the extended problem more applicable in the real lifes. Three heuristics are proposed for solving this extended p-median problem: the first is a simple heuristic algorithm; the second is a variable neighborhood search algorithm; and the third is an improved genetic algorithm. Experimental results show that the variable neighborhood search algorithm and the improved genetic algorithm are efficient for solving this problem.

Characterizations on strongly efficient solutions of set-valued optimization with generalized second-order cone-directed derivatives

XU Yihong, SUN Xin, WANG Tao

2013, 17(4): 80-86.

Asbtract ( 1019 )

PDF (577KB) ( 713 )

References | Related Articles | Metrics

The strong efficiency for set-valued optimization is considered in real normed spaces. With the help of the properties of Henig dilating cone and base functional, by applying generalized second-order cone-directed contingent derivates, a second-order optimality necessary condition is established for a pair to be a strongly efficient element of set-valued optimization whose constraint condition is determined by a set-valued mapping. When objective function is nearly cone-subconvexlike, with the scalarization theorem for a strongly efficient point an optimality sufficient condition is also derived for a pair to be a strongly efficient element of set-valued optimization.

A new solution method by linearization for a special kind of quadratic assignment problem

ZHANG Huizhen, WEI Xin, MA Liang

2013, 17(4): 87-95.

Asbtract ( 1079 )

PDF (581KB) ( 626 )

References | Related Articles | Metrics

Usually, there are many zero elements in the flow matrix and distance matrix of the quadratic assignment problem (QAP) instances abstracted from the practical problems, and the computation time of solving this kind of QAP can be dramatically decreased by using its zero elements to reduce the size of the problem. Based on the linearization of the QAP, we proposed a new solution method for the QAP with many zero elements in both flow matrix and distance matrix in this paper. Moreover, the feasibilities and advantages of solving this special kind of QAP by using the new linearization are approved from the theoretical and experimental point of view, respectively.

Online parallel batching scheduling for nonincreasing-processing-time jobs to minimize the maximum flow-time

JIAO Chengwen, LI Wenhua

2013, 17(4): 96-102.

Asbtract ( 1206 )

PDF (568KB) ( 595 )

References | Related Articles | Metrics

We consider on-line scheduling on a parallel batching machine where the jobs come with the nonincreasing-processing times. In this paper online means that jobs arrive over time. The objective is to minimize the maximum flow time of these jobs. The flow-time of a job means that its completion time minus its arrival time. It reflects the time of the job staying in the system. For the bounded model, we give a best possible algorithm with competitive ratio $\frac{1+\sqrt{5}}{2}$. For the unbounded model, we also give a best possible algorithm with competitive ratio $\sqrt{2}$.

Clique-coloring numbers of some product graphs

SHAN Erfang, YE Tingting

2013, 17(4): 103-108.

Asbtract ( 1082 )

PDF (955KB) ( 904 )

References | Related Articles | Metrics

Let G=(V, E) be a simple graph with vertex set V and edge set E. A k-clique-coloring of G is a mapping $\phi: V\rightarrow {1, 2, ..., k}, such that no maximal clique of size at least two is monochromatic. The clique-coloring number of G is the smallest k for which c is a k-clique-coloring of G. In this paper we investigate the clique-coloring numbers of Cartesian product, Kronecker product, strong product and lexicographical product of two graphs.

An optimal solution for economic production quantity models with deteriorating items and time-varying production cost

BAI Qingguo, XU Jianteng, ZHANG Yuzhong, XU Xianhao

2013, 17(4): 109-122.

Asbtract ( 1364 )

PDF (577KB) ( 1364 )

References | Related Articles | Metrics

A generalized economic production quantity model with deteriorating items over a finite planning horizon is considered in this paper. The unit production cost, the production rate and the demand rate are assumed to be known and continuous functions of time, and the forgetting effect of setup cost is incorporated into the problem. Shortages are not allowed in this model. A mixed-integer constraint optimization mathematical model in which the objective is to minimize the total cost is established and the conditions of the optimal solution for this problem are derived. A discrete variable in the total cost function is relaxed to the continuous variable and this technique is used to prove the uniqueness and optimality of the optimal solution for a special case. In addition, the optimal solution of the special case is regarded as the initial condition to simplify the search process of finding the optimal solution of the generalized problem. Finally, a numerical example is provided to illustrate the results.

Conditions of a graph being fractional k-factor-critical

LI Qiao, LIU Yan

2013, 17(4): 123-130.

Asbtract ( 1027 )

PDF (398KB) ( 574 )

References | Related Articles | Metrics

Let G be a connected undirected simple graph. If the remaining subgraph still has a fractional perfect matching after deleting any k vertices of G, the graph G is said to be fractional k-factor-critical. This paper gives sufficient conditions in terms of the toughness and the degree sum for a graph G to be fractional k-factor-critical. In some sense, we prove that the conditions are best possible. Besides, we give a necessary and sufficient condition in terms of the fractional matching number for a graph G to be fractional k-factor-critical.

Table of Content