| 查看: 305 | 回复: 0 | ||
[求助]
求教 是否此问题 已在并行调度或相关领域被研究过了？
|
|
楼主最近在研究云计算和透明计算中的调度问题，现在想到了一个简单的调度模型和解决方案，想了解是否这一块已经有人做过。虽然自己已经查阅了很多相关的文献，但是还是担心刚入这一行，掌握的信息量不够。请各位大虾指导！ 问题描述 在我们讨论多机器的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的值最小。 ” 我的问题是，是否当前已经存在相关的研究解决过这个模型类似的问题？若存在请告知相关的参考文献。谢谢！ |
回复此楼» 猜你喜欢
看来今天不会放榜了？
已经有5人回复
-
我面上完蛋了
已经有8人回复
-
只有每年这种时候来逛逛小木虫
已经有25人回复
-
什么时候开奖？
已经有7人回复
-
时间戳又变了
已经有18人回复
-
时间戳又变了8-15
已经有27人回复
-
今天基金会出结果吗？20260819
已经有16人回复
-
科研孤儿太难了
已经有16人回复
-
应该是下周三26日公布了吧？
已经有4人回复
-
投稿咨询
已经有7人回复
找到一些相关的精华帖子，希望有用哦~
【求助完结】Linux系统下MS5.5的并行计算调度问题
已经有12人回复
- 【求助】MS计算CPU占用率问题，求教
已经有17人回复
点击这里搜索更多相关资源科研从小木虫开始，人人为我，我为人人
40