24小时热门版块排行榜

返回列表

renjufyr

新虫 (初入文坛)

应助: 0 (幼儿园)
金币: 23
帖子: 5
在线: 2.6小时
虫号: 1082462
注册: 2010-08-26
性别: GG
专业: 计算机网络

[求助] 求教是否此问题已在并行调度或相关领域被研究过了？

楼主最近在研究云计算和透明计算中的调度问题，现在想到了一个简单的调度模型和解决方案，想了解是否这一块已经有人做过。虽然自己已经查阅了很多相关的文献，但是还是担心刚入这一行，掌握的信息量不够。请各位大虾指导！

问题描述

在我们讨论多机器的two-stage flowshop调度问题之前，先了解单服务器的two-stage flowshop模型。模型的描述如下：

“假设有n个客户端请求需要由1台服务器进行处理，每一个请求Ji=(di, ti)包含两个处理阶段，其中di代表磁盘读取时间，ti代表网络传输时间。用Di和Ti来代表任务Ji的磁盘读取启动时间和网络传输启动时间，那么对于所有的任务Ji和Jj，会有以下的约束条件：
　　di > 0, ti > 0,
　　Di <= Ti - di,
　　Ti <= Tj - ti or Tj <= Ti - tj,
　　Di <= Dj - di or Dj <= Di - dj;
令Jk为最后一个进行网络传输的请求，如何确定一组Sd的磁盘读取序列和一组St的网络传输序列，使得Tk+dk的值最小？”

S. M. Johnson在1954年提出这个模型的最优化解决方案，他指出对于two-stage flowshop的最优解中，St中任务的顺序必定与Sd中的顺序一致，且Sd中任务不存在时间间隙。那么，确定最优的调度序列Sd和St便只需要确定Sd即可。他根据每一个任务中di和ti的大小，将任务分为两组s1和s2，其中s1中所有任务满足di<=ti，s2中满足di>ti。那么最优调度分为两步，(1)将s1中的任务按di的大小从小到大排（用s1’表示）；(2)然后将s2中的任务按ti的大小从大到小排（用s2’表示）。这样排出来的序列s=s1’+s2’即为最佳Sd序列。

我们基于透明计算和云计算的调度原理，抽离出一种简单的调度模型，其描述为：

“对于一组客户端的任务请求{J1, J2, J3, ..., Jn}，服务器端有m台机器来并行处理。在任意时刻，每一台服务器只能处理一个任务请求，且对于每一个任务请求的响应分为两个阶段，磁盘读取和数据传送。每一个任务Ji根据其大小具有固定的磁盘读写时间di和数据传送时间ti。在每一台服务器上，任务的调度与two-stage flowshop问题一致。
　　假定起始调度时间为0，所有请求中最后被响应完成的任务为Jk，其相应的完成时间为Tk。那么，我们需要给出一种调度算法（Online or Offline），将每一个任务Ji分配到指定的服务器Mj上，并确定每一台服务器Mj上的任务调度序列Sj，以使得Tk的值最小。 ”

我的问题是，是否当前已经存在相关的研究解决过这个模型类似的问题？若存在请告知相关的参考文献。谢谢！

回复此楼