共查询到20条相似文献，搜索用时 15 毫秒
1.
Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications.
For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task
arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine
scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems
are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further
information about the tasks is available, which allows the improvement of the performance of the best possible algorithms.
Problems of this class are called semi-online ones. In this paper, the semi-online problemP2|decr|l
p (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum
of thel
p norm of every machine's load. It is shown thatLS algorithm is optimal for anyl
p norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problemsP2|online|l
p andP2|decr|l
p are presented.
Project supported by the National Natural Science Foundation of China (Nos. 10271110, 10301028) and the Teaching and Research
Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China 相似文献
2.
Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p＞1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine's load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented. 相似文献
3.
本文研究两台平行同类机的一个半在线排序问题。当机器是有准备时间的同类机时,总加工时间已知,文章给出了一个竞争比至少为的半在线算法,同时给出了证明。 相似文献
4.
WANG Yong-cai ZHAO Qian-chuan ZHENG Da-zhong 《浙江大学学报(A卷英文版)》2006,7(6):927-936
INTRODUCTION With the prevalence of distributed computing and parallel programming languages (Barry and Allen, 1998), performance evaluation of the parallel execu-tion systems becomes important. In this work we derive bounds and an approximation of the mean response time of a particular type parallel program: program with Fork-Join tasks and executed in multi-processor with first come first served (FCFS) policy. This kind of program is general in large-scale simu-lation and numerical … 相似文献
5.
6.
ZHANG Ri-dong WANG Shu-qing 《浙江大学学报(A卷英文版)》2006,7(12):1984-1988
INTRODUCTION Bilinear systems are a kind of important nonlinear systems with relatively simple structure, and many industrial processes can be described as a bilinear system. Thus research on the control of this kind of systems is very important. On the other hand, model predictive control (MPC) (Clarke et al., 1987) has been widely used in industrial applications and many predictive control methods focusing on bilinear systems are emerging (Bloemen et al., 2001; Fontes et al., 2004; He… 相似文献
7.
The choice of self-concordant functions is the key to efficient algorithms for linear and quadratic convex optimizations,
which provide a method with polynomial-time iterations to solve linear and quadratic convex optimization problems. The parameters
of a self-concordant barrier function can be used to compute the complexity bound of the proposed algorithm. In this paper,
it is proved that the finite barrier function is a local self-concordant barrier function. By deriving the local values of
parameters of this barrier function, the desired complexity bound of an interior-point algorithm based on this local self-concordant
function for linear optimization problem is obtained. The bound matches the best known bound for small-update methods.
Project supported by the National Natural Science Foundation of China (Grant No.10771133), the Shanghai Leading Academic Discipline
Project (Grant No.S30101), and the Research Foundation for the Doctoral Program of Higher Education (Grant No.200802800010) 相似文献
8.
本文提出一种交互参考方法，用于半盲情况下非线性时间序列的分析，这时描述该序列的动力学方程形式已知而相应的参数未知．通常是分别完成的噪声抑制和参数估计这２个任务在这里被组合在一起迭代完成．由于２个处理模块间的积极相互作用，该方法可获得更好的性能．以前的一些分析方法可以看作是这一处理框架的特例．将其用于含噪声混沌时间序列的分析，实验结果表明了该方法对性能的显著改善． 相似文献
9.
Ant colony algorithms comprise a novel category of evolutionary computation methods for optimization problems, especially
for sequencing-type combinatorial optimization problems. An adaptive ant colony algorithm is proposed in this paper to tackle
continuous-space optimization problems, using a new objective-function-based heuristic pheromone assignment approach for pheromone
update to filtrate solution candidates. Global optimal solutions can be reached more rapidly by self-adjusting the path searching
behaviors of the ants according to objective values. The performance of the proposed algorithm is compared with a basic ant
colony algorithm and a Square Quadratic Programming approach in solving two benchmark problems with multiple extremes. The
results indicated that the efficiency and reliability of the proposed algorithm were greatly improved.
Project (No. 9845-005) supported by National High-Tech. Research & Development Plan, China 相似文献
10.
DAVID JORDAN MARK WELLS ALEX BOZIN YASUCHI NAKAMURA ANTONY NEWMAN NJAL PETTIT 《European Journal of Engineering Education》1993,18(3):249-254
This paper reports on the incorporation of personal computers in the laboratory program at UMIST's Control Systems Centre. Laboratory practice is an integral component of all our control course. The laboratory facilities provide a mechanism for testing and verifying theoretical and design approaches. Incorporating computers in all phases of the laboratory program makes possible the use of current techniques in the analysis and design of realistic control systems. The control systems laboratory at UMIST has been developed with the goal of providing real world analysis and design experience in a laboratory setting. A collection of scale model experiments representing the major categories of industrial control problems has been constructed. These working models are coupled with a standard instrumentation interface and analogue and digital computers to implement control strategies. In all cases, great care has been taken to retain realism and allow the student to concentrate on control issues rather than configuration or programming problems. The primary objective of using personal computers in the control laboratory is to provide an on-line link between the student and the laboratory model. This provides direct ‘hands on’ experience of digital control ideas, interactive digital control experimentation and use of the computer as a multi-function virtual instrument. In addition, the computer is used off-line to simulate model performance as various control strategies are tried. At this point in time, each laboratory model station has been equipped with a personal computer containing A/D and D/A converters, hard and floppy disk, and a real-time clock. The computers are networked to provide access to printing and file storage facilities. Originally the software packages were written primarily in BASIC, and ran on BBC computers. These versions are however in the process of being replaced by PC-based packages written in C. Both the original BASIC and the C-successors have been developed to provide interactive, real-time control of the model using a choice of digital control algorithms. Using the keyboard as a control panel, the student can observe model performance, vary controller parameters, choose display characteristics and record parametric and graphical data. Future developments will expand the choice of available control algorithms and enhance the off-line analysis and design tools. 相似文献
11.
Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines 总被引：1，自引：0，他引：1
INTRODUCTION Sequencing and scheduling are forms of deci-sion-making which play a crucial role in most manufacturing and production systems as well as in most information-processing environments, and also exist in transportation and distribution settings and in other types of service industries. A scheduling problem is called on-line if it re-quires scheduling jobs irrevocably on the machines as soon as they are given, without any knowledge about jobs that follow later on. If we have full… 相似文献
12.
In this paper, a semi on-line version on m identical machines M1, M2, …,Mm(m≥3) was considered, where the processing time of the largest job is known in advance. Our goal is to maximize the minimum machine load, an NPLS algorithm was presented and its worst-case ratio was proved to be equal to m-1 which is the best possible value. It is concluded that if the total processing time of jobs is also known to be greater than (2m-1)pmax where pmax is the largest job's processing time, then the worst-case ratio is 2-1/m. 相似文献
13.
针对MapReduce任务调度中任务属性取默认值的不合理性以及人为指定值的不确定性,对调度算法实现动态调整任务优先级、计算合理的Reduce任务数、明确Reduce任务启动时机等改进,达到提升任务并行度、缩短作业执行时间的目的.Fair与LATE算法改进前后的实验结果表明,基于任务属性的改进能提高调度算法性能与作业整体执行效率. 相似文献
14.
基于启发式算法的工作流调度算法目标单一,无法保证用户满意度,且多目标调度算法少、性能差。为了改善现状,提出基于多阶段PSO的多目标工作流调度算法MSPSO,分析工作流任务的层次结构,按层次进行多阶段PSO调度,结合排队理论估算每阶段调度需要的虚拟机数量,控制PSO搜索空间,使算法能快速找到最优解。用4种真实科学工作流在CloudSim环境下进行仿真实验。结果表明,MSPSO算法资源利用率提高了1.81%,能耗降低了9.16%,任务违约率低至0.075%。MSPSO调度算法不仅能动态增减虚拟机,降低能耗,还能在保证截止时间的前提下降低任务违约率,提高资源利用率。 相似文献
15.
孔晓红 《河南科技学院学报》2007,35(2):46-49
目前大规模的并行分布多处理机系统中,调度算法好坏直接影响计算系统的高性能计算潜力能否发挥,调度的目的就是如何分配资源使系统性能最优。本文主要讨论分布式多处理机系统进行任务调度时的关键问题,包括问题模型的描述,调度策略,常用算法,评估标准,数据平台以及该问题的发展趋势。 相似文献
16.
If the measuring signals were input to the chaotic dynamic system as initial parameters, the system outputs might be in steady
state, periodic state or chaos state. If the chaotic dynamic system outputs controlled in the periodic states, the periodic
numbers would be changed most with the signals. Our novel method is to add chaotic dynamic vibration to the measurement or
sensor system. The sensor sensitivity and precision of a measurement system would be improved with this method. Chaotic dynamics
measurement algorithms are given and their sensitivity to parameters are analyzed in this paper. The effects of noises on
the system are discussed.
Project support by the National Natural Science Foundation of China (No. 59805017) and the 863 High-Technology Project of
China (No. 863-512-9805-08). 相似文献
17.
On-line topical importance estimation: an effective focused crawling algorithm combining link and content analysis 总被引：2，自引：0，他引：2
Can Wang Zi-yu Guan Chun Chen Jia-jun Bu Jun-feng Wang Huai-zhong Lin 《浙江大学学报(A卷英文版)》2009,10(8):1114-1124
Focused crawling is an important technique for topical resource discovery on the Web. The key issue in focused crawling is to prioritize uncrawled uniform resource locators （URLs） in the frontier to focus the crawling on relevant pages. Traditional focused crawlers mainly rely on content analysis. Link-based techniques are not effectively exploited despite their usefulness. In this paper, we propose a new frontier prioritizing algorithm, namely the on-line topical importance estimation （OTIE） algorithm. OTIE combines link- and content-based analysis to evaluate the priority of an uncrawled URL in the frontier. We performed real crawling experiments over 30 topics selected from the Open Directory Project （ODP） and compared harvest rate and target recall of the four crawling algorithms： breadth-first, link-context-prediction, on-line page importance computation （OPIC） and our OTIE. Experimental results showed that OTIE significantly outperforms the other three algorithms on the average target recall while maintaining an acceptable harvest rate. Moreover, OTIE is much faster than the traditional focused crawling algorithm. 相似文献
18.
This experiment investigated metacognitive monitoring in the processing of anaphors in 10–year-old skilled and less skilled comprehenders. Two tasks were used with expository texts. The direct self-evaluation task was carried out with consistent texts in which target anaphors were either repeated noun phrases or pronouns. Subjects had to read and to evaluate their own comprehension on a 6–point scale. After reading, subjects answered multiple-choice questions designed to test the processing of anaphors. In the inconsistency detection task, target anaphors were either repeated noun phrases or inconsistent noun phrases. Subjects had to read and detect inconsistencies. After reading, they answered multiple-choice questions. In both tasks, on-line measures (reading times for units containing target anaphors and for subsequent units, and look-backs) were collected in addition to off-line measures (ratings of comprehension, detection of inconsistencies and response to multiple-choice questions) in order to analyse indicators of implicit and explicit evaluation and revision activities. The results from the two tasks converged: less skilled comprehenders showed deficiencies in monitoring on measures of implicit and explicit evaluation and revision. Patterns of reading times revealed that less skilled comprehenders were sensitive to the difficulties in processing pronouns in the self-evaluation task and also sensitive to the lack of text cohesion in the inconsistency detection task. However, this sensitivity was weak and unable to trigger explicit activities. These results were interpreted in the framework of Karmiloff-Smith's (1986) model. 相似文献
19.
This paper explores brain CT slices segmentation technique and some related problems, including contours segmentation algorithms,
edge detector, algorithm evaluation and experimental results. This article describes a method for contour-based segmentation
of anatomical structures in 3D medical data sets. With this method, the user manually traces one or more 2D contours of an
anatomical structure of interest on parallel planes arbitrarily cutting the data set. The experimental results showed the
segmentation based on 3D brain volume and 2D CT slices. The main creative contributions in this paper are: (1) contours segmentation
algorithm; (2) edge detector; (3) algorithm evaluation.
Project (No.69931010) supported by the National Natural Science Foundation of China 相似文献
20.
Robust video foreground segmentation and face recognition 总被引：1，自引：0，他引：1
管业鹏 《上海大学学报(英文版)》2009,13(4):311-315
Face recognition provides a natural visual interface for human computer interaction (HCI) applications. The process of face
recognition, however, is inhibited by variations in the appearance of face images caused by changes in lighting, expression,
viewpoint, aging and introduction of occlusion. Although various algorithms have been presented for face recognition, face
recognition is still a very challenging topic. A novel approach of real time face recognition for HCI is proposed in the paper.
In view of the limits of the popular approaches to foreground segmentation, wavelet multi-scale transform based background
subtraction is developed to extract foreground objects. The optimal selection of the threshold is automatically determined,
which does not require any complex supervised training or manual experimental calibration. A robust real time face recognition
algorithm is presented, which combines the projection matrixes without iteration and kernel Fisher discriminant analysis (KFDA)
to overcome some difficulties existing in the real face recognition. Superior performance of the proposed algorithm is demonstrated
by comparing with other algorithms through experiments. The proposed algorithm can also be applied to the video image sequences
of natural HCI.
Project supported by the National Natural Science Foundation of China (Grant No.60872117), and the Leading Academic Discipline
Project of Shanghai Municipal Education Commission (Grant No.J50104) 相似文献