共查询到20条相似文献,搜索用时 0 毫秒
1.
Scheduling a Single Server in a Two-machine Flow Shop 总被引:1,自引:0,他引:1
We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one
machine to the other. The problem with a given job sequence is shown to be reducible to a single machine batching problem.
This result enables several cases of the server scheduling problem to be solved in O(n log n) by known algorithms, namely, finding a schedule feasible with respect to a given set of deadlines, minimizing the maximum
lateness and, if the job processing times are agreeable, minimizing the total completion time. Minimizing the total weighted
completion time is shown to be NP-hard in the strong sense. Two pseudopolynomial dynamic programming algorithms are presented
for minimizing the weighted number of late jobs. Minimizing the number of late jobs is proved to be NP-hard even if setup
times are equal and there are two distinct due dates. This problem is solved in O(n
3) time when all job processing times on the first machine are equal, and it is solved in O(n
4) time when all processing times on the second machine are equal.
Received November 20, 2001; revised October 18, 2002
Published online: January 16, 2003 相似文献
2.
3.
Ralph P. Massaro 《Information Security Journal: A Global Perspective》2013,22(3):38-45
For years, the mainstay of corporate computing has been the centralized mainframe—a behemoth caged in a climate-controlled glass house. In most cases, this mainframe is an IBM or IBM-compatible computer running the MVS operating system and operating as either a standalone system or as part of a limited, proprietary network of mainframes within the same organization. Security on these mainframe systems has improved over time, as management has come to understand its importance and as vendors have developed and marketed access control software that is both effective and easy to use. For example, most of these systems operate with one of the major access control packages (IBM's RACF or Computer Associates' CA=ACF2 or CA=Top Secret). 相似文献
4.
《Advanced Robotics》2013,27(11-12):1557-1576
In a floor warehouse environment, where many agents transport numbers of products iteratively, efficient product transportation is required for high productivity. In general, the following facts are recognized. (i) Three kinds of jobs exist: picking, replenishment and arrangement. (ii) Mixed-load transportation can decrease the completion time of vehicles. In many former methods, however, the above facts are not considered. We propose a design methodology using a dispatching rule and a local search method based on a simulated annealing algorithm. The rule is applied to obtain the initial solution and the local search method is adopted to obtain a semi-optimal solution in consideration of mixed-load transportation. To evaluate the applicability of the proposed algorithm, we have implemented the algorithm in several product environments. The simulation results verify the effectiveness of the proposed method. 相似文献
5.
在云制造环境下, 制造资源和制造能力以服务的形式封装起来, 不同的任务通过云端汇集到云平台并通过合适的调度给每个任务分配相应的服务. 由于任务在执行的过程中的不确定性, 会在某个时刻遇到突发状况从而导致对余下任务的重调度问题. 因此, 针对该问题, 考虑到云制造环境下任务的复杂性和多样性会导致在合理的时间段内很难找到最优解, 以所有任务的最大完成时间为优化目标, 提出了一种以改进的遗传算法与邻域搜索技术相结合的元启发式算法, 旨在解决云制造环境下由于任务和资源服务等的不确定性导致的重调度问题. 实验结果表明,本文所提出的算法能够很好地解决动态调度过程中的重调度问题, 并可以快速地获取最优解. 相似文献
6.
基于多媒体服务器的性能要求,提出了一种自适应的混合磁盘调度策略DRT-window.它既能满足实时请求对实时性的要求,根据实时请求的截止期动态选择窗口大小;又能在其松弛度内尽努力(best-effort)地服务非实时请求,从而减少非实时请求的响应时间。DRT-window采用了两级层次调度方案:第一层为不同类型的请求采用各自适合的调度策略;第二层为混合请求调度嚣,混合调度第一层中的不同类型的请求。通过性能比较和理论证明,表明此混合磁盘调度策略能在保证实时请求无抖动执行的同时,尽量地减少非实时请求的响应时间。 相似文献
7.
一种多媒体服务器的技术方案 总被引:1,自引:0,他引:1
通过对多媒体信息传输内容和具体的软硬件分析,提出了视频“流”机制的传输方案,进而介绍了基于“流”技术的多媒体服务器组成及其教学应用。 相似文献
8.
云系统中面向海量多媒体数据的动态任务调度算法 总被引:1,自引:0,他引:1
在云计算环境下,对处理海量多媒体数据的作业以及任务调度与资源分配算法进行建模,在此模型下提出一种云计算环境下面向海量多媒体数据的动态任务调度算法.算法以云系统中海量多媒体数据文件的分块多副本存储形式为基础来规划并行处理任务,以文件块和副本的映射关系为特征对云系统中数据节点执行聚类,以已执行完毕任务的历史反馈信息为基础来动态调度未执行任务.实验结果表明提出的算法对提高系统资源利用率和负载均衡有显著效果. 相似文献
9.
目前采用集群技术是实现大规模视频服务的主要手段.本文在通过分析Linux服务器集群系统(LVS)的特点,视频服务器集群系统的负载调度研究中,针对请求的服务时间变化大的特点,提出一种动态反馈负载平衡算法,它结合内核中的加权连接调度算法,根据动态反馈回来的负载信息来调整服务器的权值,从而有效地解决服务器间的负载不平衡问题,提高了系统的吞吐率,使整个集群的综合负载率随规模增大而呈平滑增长. 相似文献
10.
随着计算规模不断扩大,人们对并行计算调度的性能要求也不断提高。网格技术的出现,解决了计算资源的共享性、异构性、规模可扩展性、鲁棒性以及安全性等方面的问题,但同时也在资源调度方面带来了新的挑战。HITGRID是一个基于Globus网格工具平台上的网格调度中间件,它接收用户提交的计算任务,针对用户对计算资源提出的要求,在网格环境中查找符合条件的资源进行调度。文中讨论了将NWS预测技术封装为标准网格资源信息的方法,以及资源调度的性能模型,给出了调度中资源选择的策略。最后通过一个计算大规模N体问题的实例表明笔者的工作是有成效的。 相似文献
11.
In this paper, we address the problem of scheduling communication over the interconnection network of a distributed-memory multicomputer video server. We show that this problem is closely related to the problem of data distribution and movie scheduling in such a system. A solution is proposed in this paper that addresses these three issues at once. The movies are distributed evenly over all nodes of the multicomputer. The proposed solution minimizes the contention for links over the switch. The proposed solution makes movie scheduling very simple—if the first block of the movie is scheduled, the rest of the movie is automatically scheduled. Moreover, if the first block of the movie stream is scheduled without network contention, the proposed solution guarantees that there will be no network contention during the entire duration of playback of that movie. We show that the proposed approach to communication scheduling is optimal in utilizing the network resources. Extensive simulation results are presented to show the effectiveness of the proposed approach. 相似文献
12.
13.
14.
15.
分布式多媒体系统的核心问题是多媒体流的服务质量(QoS)保证,越来越多的系统通过QoS管理来实现多媒体服务的QoS保证,国际上不同组织和团体提出不同的管理机制和策略,比较著名的有:1)IETF提出的Internet综合业务模型(IIS),定义了实现应用的QoS保证的结构,关键研究工作是资源预留协议和IIS模型在网络层次之间的QoS映射;2)ISO/OSI提 相似文献
16.
仿真网格是以通用网格技术为基础、面向仿真领域的专用网格,目前国际上对仿真网格的研究尚处于起步阶段.现有的分布式仿真HLA(high level architecture)体系结构中的仿真资源和联邦成员是静态绑定的,网格技术的引入使得仿真资源的动态分配成为可能.根据仿真网格任务调度的特点,在仿真网格中建立了一种任务调度模型,并针对该模型,提出了一种新的基于知识的动态任务调度算法KMO,该算法适用于将N个相互独立的计算需求不同的仿真任务调度到M个随时间动态变化的仿真资源上,它能对若干次调度后的结果进行统计并提炼成"知识"反馈给算法预处理部分,使得该算法在动态多变的环境中能获得比较稳定的性能.实验结果表明,在仿真网格环境中,该算法的性能优于网格中传统的任务调度算法. 相似文献
17.
随着计算机技术的发展与用户需求的不断提升,多有向无环图(DAG)共享一组异构计算资源的问题受到广泛的关注。但由于实际任务的复杂多变,多个DAG之间存在一定的差异,导致多DAG调度策略存在公平性问题。为此,提出一种改进的启发式公平调度算法IFairness。在选择待调度DAG阶段采用一种新的评判指标DAG完成度,代替原Fairness算法中的剩余Makespan作为DAG选择依据,在计算每个DAG的滞后程度阶段,采用"向后看"一步的原则,解决某些DAG在初期得不到调度的问题。仿真结果表明,与原Fairness算法相比,IFairness算法不公平程度降低了7.28%,资源利用率提升了11.97%,有效提高了调度算法的公平性及资源利用率。 相似文献
18.
19.
Shim Simon S.Y. Chang Tai-Sheng Du David H.C. Hsieh Jenwei Wang Yuewei 《Multimedia Tools and Applications》2002,18(1):31-54
The existing SCSI parallel bus has been widely used in various multimedia applications. However, due to the unfair bus accesses the SCSI bus may not be able to fully utilize the potential aggregate throughput of disks. The number of disks that can be attached to the SCSI bus is limited, and link level fault tolerance is not provided. The serial storage interfaces such as Serial Storage Architecture (SSA) provide high data bandwidth, fair accesses, long transmission distance between adjacent devices (disks or hosts) and link level fault tolerance. The fairness algorithm of SSA ensures a fraction of data bandwidth to be allocated to each device. In this paper we would like to know whether SSA is a better alternative in supporting continuous media than SCSI. The scalability of a multimedia server is very important since the storage requirement may grow incrementally as more contents are created and stored. SSA in a shared-storage cluster environment also supports concurrent accesses by different hosts as long as their access paths are not overlapped. This feature is called spatial reuse. Therefore, the effective bandwidth over an SSA can be higher than the raw data bandwidth and the spatial reuse feature is critical to the scalability of a multimedia server. This feature is also included in FC-AL3 with a new mode called Multiple Circuit Mode (MCM). Using MCM, all devices can transfer data simultaneously without collision. In this paper we have investigated the scalability of shared-stroage clusters over an SSA environment. 相似文献
20.
Graphical Transformation of Multimedia XML Documents 总被引:1,自引:0,他引:1
As a commonly acceptable standard for guiding Web markup documents, XML allows the Internet users to create multimedia documents of their preferred structures and share with other people. The creation of various multimedia document structures, typically as trees, implies that some kinds of conversion mechanisms are needed for people using different structures to understand each other. This paper presents a visual approach to the representation and validation of multimedia document structures specified in XML and transformation of one structure to another. The underlying theory of our approach is a context-sensitive graph grammar formalism. The paper demonstrates the conciseness and expressiveness of the graph grammar formalism. An example XML structure is provided and its graph grammar representation, validation and transformation to a multimedia representation are presented. 相似文献