排序方式: 共有14条查询结果,搜索用时 15 毫秒
1.
2.
3.
Feifeng Zheng E. Zhang Yinfeng Xu Wei-Chiang Hong 《Journal of Combinatorial Optimization》2014,27(1):182-198
This paper makes extended studies on the discrete problem of online scheduling and reliable lead time quotation (discrete Q-SLTQ) introduced by Keskinocak et al. (Manag. Sci. 47(2):264–279, 2001). We first relax the assumption on revenue function from a linear decreasing function to any decreasing function. We present an online deterministic strategy which is optimal in competitiveness for concave revenue functions. The above results are further extended to the continuous Q-SLTQ model where orders are released at arbitrary time points. For the discrete Q-SLTQ problem, if orders are with nonuniform lengths, we prove the nonexistence of online strategies with bounded competitive ratios; otherwise if orders are with unit length but various weights, we present an optimal online strategy. 相似文献
4.
Jidan Huang Feifeng Zheng Yinfeng Xu Ming Liu 《Journal of Combinatorial Optimization》2018,35(1):216-223
In this work we investigate the online over-list MapReduce processing problem on two identical parallel machines, aiming at minimizing the makespan. Jobs are revealed one by one, and each job consists of one map task and one reduce task. The map task can be arbitrarily split and processed on both machines simultaneously, while the reduce task has to be processed on a single machine and it cannot be started unless the map task has been completed. We first show that the general case of the problem reduces to the classical two machine online scheduling model with an optimal competitive ratio of 3/2. For a special case where the map task is at least as long as the reduce task, we prove that no online algorithm can be less than 4/3-competitive. An optimal Greedy algorithm with a matching competitive ratio is proposed as well. 相似文献
5.
Xin Feng Yongxi Cheng Feifeng Zheng Yinfeng Xu 《Journal of Combinatorial Optimization》2016,31(4):1569-1585
We study an integrated production–distribution scheduling problem where jobs are released by customers to a manufacturer over time. The jobs are released online, that is, at any time the information of the number, release and processing times of future jobs is unknown, and the processing time of a job becomes known when the job is released. The manufacturer processes the jobs on a single machine. During the processing of jobs preemption is not allowed. Completed jobs are delivered in batches to customers via sufficient capacitated vehicles. For the objective of minimizing the sum of the total delivery time and the total distribution cost, we present a 3-competitive algorithm for the single-customer case and then extend the result to the multi-customer case. A lower bound of two on the competitive ratio of the problem is also given. 相似文献
6.
Stanley P. Y. Fung Chung Keung Poon Feifeng Zheng 《Journal of Combinatorial Optimization》2008,16(3):248-262
We consider the problem of scheduling a set of equal-length intervals arriving online, where each interval is associated with
a weight and the objective is to maximize the total weight of completed intervals. An optimal 4-competitive algorithm has
long been known in the deterministic case, but the randomized case remains open. We give the first randomized algorithm for
this problem, achieving a competitive ratio of 3.5822. We also prove a randomized lower bound of 4/3, which is an improvement
over the previous 5/4 result. Then we show that the techniques can be carried to the deterministic multiprocessor case, giving
a 3.5822-competitive 2-processor algorithm, and a 4/3 lower bound for any number of processors. We also give a lower bound
of 2 for the case of two processors.
A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 176–186.
The work described in this paper was fully supported by a grant from City University of Hong Kong (SRG 7001969), and NSFC
Grant No. 70525004 and 70702030. 相似文献
7.
本文通过对耒阳市暑假期间农村中小学生流动情况的考察。发现暑假期间外出的农村中小学生规模相当宏大,形成了一股与“民工潮”相对的“学生潮”。本文提出“学生潮”的概念,并揭示和剖析出“学生潮”与“民工潮”之间的内在复杂关系以及“学生潮”对社会尤其是对教育的负面影响。 相似文献
8.
This paper studies the on-line production order scheduling problem where each preemption causes a penalty, and the objective
is to maximize the net profit, i.e., the total weights of completed orders minus the total penalties caused by preemptions.
Two greedy strategies are shown to be at best and -competitive respectively, where Δ is the ratio between the longest and shortest length of order. After that we mainly present
an improved strategy, named WAL, which takes advantage of the knowledge of Δ and is proved to be -competitive for Δ > 9. Furthermore, two lower bounds for deterministic strategies, and 6.33, are given for the cases of nonuniform and uniform length respectively.
This research is supported by NSF of China under Grants 70471035, 70525004, 70121001 and 70602031. 相似文献
9.
Ming Liu Chengbin Chu Yinfeng Xu Feifeng Zheng 《Journal of Combinatorial Optimization》2011,21(1):138-149
We study the problem of semi-online scheduling on 2 machines under a grade of service (GoS). GoS means that some jobs have
to be processed by some machines to be guaranteed a high quality. The problem is online in the sense that jobs are presented
one by one, and each job shall be assigned to a time slot on its arrival. Assume that the processing time p
i
of every job J
i
is bounded by an interval [a,α
a], where a>0 and α>1 are two constant numbers. By knowing the bound of jobs’ processing times, we denote it by semi-online problem. We deal
with two semi-online problems. 相似文献
10.
Wenming Zhang Yinfeng Xu Feifeng Zheng Yucheng Dong 《Journal of Combinatorial Optimization》2012,23(2):159-166
The basic models of online time series search and one-way trading are introduced by El-Yaniv et al. in Algorithmica 30(1),
101–139 (2001) where it is assumed that the prices are bounded within interval [m,M] (0<m<M). In this paper, we consider another case where every two consecutive prices are interrelated, that is, the variation range
of each price depends on its preceding price. We present optimal deterministic online algorithms for the two problems, respectively.
According to one conclusion in Algorithmica 30(1), 101–139 (2001), we further point out that for the case we considered, an optimal deterministic algorithm for the one-way trading problem
can be regarded as an optimal randomized one for the time series search problem, and randomization is useless for the one-way
trading problem. 相似文献