标签: resource-scheduling

我知道有一些调度问题是NP-hard/NP-complete ...但是,没有一个以这样的方式表明这种情况也是NP.

如果您有一组约束到startAfter,startBy和duration的任务,所有尝试使用单个资源 ...您是否可以解决计划或确定无法在没有详尽搜索的情况下解决它？

如果答案是"对不起,但这是NP完全",那么最好的启发式(s？)是什么,并且有办法减少a)解决时间表和b)识别无法解决的时间时间表.

我通过实现"最小窗口优先"启发式的递归实现了(在prolog中)一个基本的冲突解决目标.这实际上很快找到了解决方案,但在查找无效的计划时非常慢.有办法克服这个问题吗？

耶和复合问题!

我有一个优化问题.这是一个包含20个部分的产品(生产顺序无关紧要).我有3台类似的机器可以生产所有20个零件.

我用分钟表示了20个部分(即生产第一部分需要3分钟,生产第二部分需要75分钟等)

ItemTime<-c(3,75,55,12,45,55,11,8,21,16,65,28,84,3,58,46,5,84,8,48)

因此生产1种产品需要730分钟.

sum(ItemTime)

目的是通过将好的物品分配给三台机器来最小化一种产品的生产.

sum(ItemTime/3)

所以实际上我需要尽可能接近243.333分钟(730/3)

可能性的数量巨大3 ^ 20

我想有许多不同的最佳解决方案.我希望R给我所有这些.我不需要知道需要机器1 2和3的总时间:我还需要知道给机器1,机器2和机器3提供哪些物品.

或者,如果它太长,我想选择一个尽可能合理的样本而不重复......

我可以用R语言解决我的问题吗？

我在这里的第一篇文章 - 希望你能帮助我设计一个我一直在考虑一段时间的算法 - 不知道采取什么方法(VRPTW或资源调度或完全不同的东西!？)

把它变成一个真实的例子,我们在少数地方(通常少于5个)有很多花园垃圾.必须在规定的时间内将废物全部运送到其他地方.为了搬运花园垃圾,我们有拖车,必须用汽车牵引.花园垃圾只能在特定时间(时间窗口)掉落在垃圾场.在某些地方,我们可以放下拖车,由那里的人填满或清空,但在其他地方,汽车的司机必须自己做,汽车必须留在那里.可以计算所有时间(即装载/卸载时间,运输时间等).汽车可以在没有拖车的地点之间移动,拖车可以拖空,但拖车不能在不同地点之间移动.

我们的目标是确保所有拖车装载的废物同时运输

• 尽量减少使用中的拖车和汽车数量
• 满足所有时间窗口,以减少浪费
• "平衡"预告片 - 即在一天结束时,我们在每个地点都有与当天开始时一样多的预告片

我想过将其作为一种资源调度算法,但我不确定如何处理预告片的"平衡".

我考虑的另一种方法是首先考虑汽车.然后我可以选择最早的任务并在此之后构建所有可行任务的图表.如果我然后选择通过图表的最长路径,该路径将服务于最大数量的拖车负载.然后,我可以从任务列表中删除这些任务并重复,直到所有任务都得到服务.然后,我需要检查这些拖车负载列表,以计算出所需的拖车数量.

任何关于接近的想法将不胜感激!

我正在尝试使用SWI prolog和CLP进行项目调度.我设法支持顺序依赖,但我正在努力避免双重预订人.

我有一个名为Schedule的列表,其中包含[taskname,starttime]等元素,其中starttime是约束求解器的自由变量.它们已经受到顺序依赖性的限制.

我正在尝试编写一个这样的循环来排除双重预订:

  forall /* or maybe foreach*/ (isa(P,person), (
    % Filter scheduled tasks on that person...
    include(\[T,S]^(assigned(T,P)), Schedule, HisSchedule),
    % Present what serialized expects..
    maplist(\[T,S]^S^true, HisSchedule, Sts),
    % duration is just user-defined data... 
    maplist(\[T,S]^D^(duration(T,D)), HisSchedule, Dus),
    % Hit it...
    serialized(Sts, Dus)
  )),

随着foreach它总是失败和forall它总是成功而不会约束任何东西.

就这个循环而言,Schedule是全局的,目的是使用序列化来约束其starttime元素.OTOH,HisSchedule,Sts和Dus取决于特定的人.因此,我认为我需要foreach让Schedule快乐,但是要让HisSchedule等快乐.那是问题吗？如果是这样,我该如何解决？

我一直在网上寻找一段时间,试图找到这两个术语的定义和例子,但我似乎无法得到一个直接的答案,我只是变得更加困惑.

有人可以向我解释一下这个区别.一篇好的描述性文章会有所帮助.

我正在开发一个Java应用程序,它应该允许用户优化他们的日程安排.为此,我需要一个框架来帮助计算"任务"的最佳时间,注意:

1. 所需的资源和资源使用限制
2. 任务之间的依赖关系(虽然只能与F-> S关系)
3. 最早和最晚的开始 - 结束时间,松弛时间
4. 基线与实际时间 - 允许报告实际的开始和结束时间,相应地更新其余任务

一些澄清:我既不是在寻找一个框架来绘制这些甘特,也不是在寻找一个处理一个特定问题领域的框架(如教室),而且绝对不是一个处理线程调度的框架.

谢谢!

我有一堆工作需要在特定的时间间隔执行.但是,我们每天都有足够的资源来完成这项工作.因此,我试图优化开始时间日期(开始时间日期只能向前移动而不是向后移动),这样每天使用的资源与我们预算的资源更不相似.

这些函数在下面的示例中使用::

# Function to shift/rotate a vector
shifter <- function(x, n = 1) {
  if (n == 0) x else c(tail(x, -n), head(x, n))
}

# Getting a range of dates
get_date_range <- function(current_date = Sys.Date(), next_planned_date = Sys.Date() + 5)
{
  seq.Date(as.Date(current_date), as.Date(next_planned_date), "days")
}

假设玩具示例数据集::此处任务P1在14日开始,而P2从15日开始.值零表示当天没有为该任务完成任务.

# EXAMPLE TOY DATASET 
datain = data.frame(dated = c("2018-12-14", "2018-12-15", "2018-12-16", "2018-12-17"), 
                    P1 = c(1,2,0,3), P2 = c(0,4,0,6)) %>%
  mutate(dated = as.character(dated)) 

#The amount of resources that can be  used in a …

我正在处理的软件应用程序需要能够根据当前拥有的任务数量为一组用户分配任务,其中具有最少任务的用户最有可能完成下一个任务.但是,当前任务负载应被视为加权,而不是绝对订单定义.IOW,我需要实现一个加权的负载平衡算法.

假设有五个用户,具有以下任务数:

A:4 B:5 C:0 D:7 E:9

我想为CABDE命令中的下一个任务确定用户的优先级,其中C最有可能获得分配,E最不可能.这里有两件重要的事情需要注意:

• 用户数量可以从2到数十个不等.
• 分配给每个用户的任务数量可以从1到数百不等.

就目前而言,我们可以将所有任务视为平等,但我不介意将任务困难作为我将来可以使用的变量 - 但这纯粹是锦上添花.

到目前为止我提出的想法在某些情况下并不是很好.如果用户数量很多,他们可能会过度密切地对用户进行加权,如果用户没有当前任务,他们可能会失败,或者....

我试过在网上闲逛,但运气不好.任何人都可以给我一个运行良好的算法的快速摘要吗？我不需要实际的实现 - 我会做那部分 - 只是一个很好的描述.另外,有一个可以免费访问的好网站吗？

此外,虽然我当然欣赏质量,但这不一定在统计上是完美的.所以,如果你能想到一个好但不是很好的技术,我很感兴趣!