是否有一个调度算法，优化了＆QUOT;制造商的时间表＆QUOT;？ [英] Is there a scheduling algorithm that optimizes for "maker's schedules"?

问题描述

您可能熟悉保罗·格雷厄姆的文章， 设备的日程安排，经理的时间表 。破题的关键在于创意和专业技术人员，会议是诅咒的生产力，因为他们往往​​会导致时间表碎片化，打破了空闲时间成块太小获得解决疑难问题所需的重点。

You may be familiar with Paul Graham's essay, "Maker's Schedule, Manager's Schedule". The crux of the essay is that for creative and technical professionals, meetings are anathema to productivity, because they tend to lead to "schedule fragmentation", breaking up free time into chunks that are too small to acquire the focus needed to solve difficult problems.

在我的公司，我们已经看到了通过减少造成的破坏量显著的好处，但蛮力算法，我们用它来确定的时间表是不够成熟的处理安排一大群人很好。 （*）

In my firm we've seen significant benefits by minimizing the amount of disruption caused, but the brute-force algorithm we use to decide schedules is not sophisticated enough to handle scheduling large groups of people well. (*)

我正在寻找的是，如果有任何众所周知的算法，最大限度地减少这种生产力的破坏，在一组的 N 的制定者和管理者。

What I'm looking for is if there's are any well-known algorithms which minimize this productivity disruption, among a group of N makers and managers.

在我们的模型中，

• 有 N 的人。
• 在每个人的 P <子>我 的要么是机的（的Mk 的）或者管理（镁的）。
• 每个人都有一个时间表的取值<子>我 的
• 在每个人的日程安排的 ^ h 的小时之久。
• 时间表由一系列非重叠的时间间隔的取值<子>我 的= [ ^ h <子> 1 的。 ..，的 ^ h <子>Ĵ 的。
• 在一个时间间隔可以是的免费或忙的。两个相邻的自由间隔相当于一个免费的间隔跨越两个。
• 的生产率的 P 的每个人是0和1之间的值。
  • 当空闲间隔数最小化制造商的生产效率最大化。
  • 甲机的生产力是等于1 /（最大值[1，游离的间隔数]）。
  • 当空闲时间的总长度被最大化经理的工作效率最大化，但他们喜欢的聚会超过短暂的休息之间的很长一段。
  • 甲经理的生产率等于每个自由间隔为一天中的某个比例的长度的平方和。也就是说，（ ^ h <子> 1 / S <子>我 的） ² +（ ^ h ₂ / S <子>我 的） ² + ...，其中每个时间间隔是一个免费的区间。
  • There are N people.
  • Each person p_i is either a maker (Mk) or a manager (Mg).
  • Each person has a schedule s_i.
  • Everyone's schedule is H hours long.
  • A schedule consists of a series of non-overlapping intervals s_i = [h₁, ..., h_j].
  • An interval is either free or busy. Two adjacent free intervals are equivalent to a single free interval that spans both.
  • The productivity P for each person is a value between 0 and 1.
    • A maker's productivity is maximized when the number of free intervals is minimized.
    • A maker's productivity is equal to 1 / (max[1, the number of free intervals]).
    • A manager's productivity is maximized when the total length of free time is maximized, but they like long stretches between meetings more than short breaks.
    • A manager's productivity is equal to the sum of the squares of the lengths of each free interval as a proportion of the day. That is, (h₁/s_i)² + (h₂/s_i)² + ... , where each interval is a free interval.

    请注意，如果没有会议，无论是决策者和管理者体验最佳的生产率。如果会议必须安排，那么厂商preFER的会议正好背到后面，而管理者不关心会议去。需要注意的是，因为所有的中断都被视为同样有害于制造商，有一个会议，持续1秒，会议，持续到3小时之间没有什么区别，如果段的可用时间。

    Notice that if there are no meetings, both the makers and the managers experience optimum productivity. If meetings must be scheduled, then makers prefer that meetings happen back-to-back, while managers don't care where the meeting goes. Note that because all disruptions are treated as equally harmful to makers, there's no difference between a meeting that lasts 1 second and a meeting that lasts 3 hours if it segments the available free time.

    现在的问题是，以决定如何安排的 M 的不同的会议包括任意数目的 N 的人，每个人在一次会议必须放置的忙的间隔成他们的日程安排，使得它不与任何其它的忙的间隔重叠。对于每次会议的 M <子> T 的开始时间的忙的间隔必须是相同的所有各方。

    The problem is to decide how to schedule M different meetings involving arbitrary numbers of the N people, where each person in a given meeting must place a busy interval into their schedule such that it doesn't overlap with any other busy interval. For each meeting M_t the start time for the busy interval must be the same for all parties.

    有没有一种算法存在解决这个问题，或一个类似于它？我首先想到的是，这看起来非常相似，碎片整理（最小化不同的块数），并有大量的关于算法。但是，碎片整理不会有很多工作要做，调度。思考？

    Does an algorithm exist to solve this problem or one similar to it? My first thought was that this looks really similar to defragmentation (minimize number of distinct chunks), and there are a lot of algorithms about that. But defragmentation doesn't have much to do with scheduling. Thoughts?

    （*）实事求是地讲，这不是一个真正的问题，因为它是罕见的，我们的会议有超过〜5人一次，所以可能性的空间小。

    (*) Practically speaking this is not really a problem, because it's rare that we have meetings with more than ~5 people at once, so the space of possibilities is small.

    推荐答案

    一个很好的近似，这可以通过使用遗传算法可以了。

    A good approximation for this can be had by the use of a Genetic algorithm.

    编写一个函数来创建1000个样本的随机调度分配者和管理者随机。

    Write a function to create 1000 sample random schedules assigning makers and managers randomly.

    写另一个函数（适应度函数）来分配记过至时间表有问题的（人在同一时间的工作，没有足够的人员，没有足够的管理人员，一个人没有足够的工作，一个人的工作太多了）。

    Write another function (fitness function) that assigns demerits to schedules with problems (people working at the same time, not enough makers, not enough managers, someone not worked enough, someone worked too much).

    foreach schedule assign calculate fitness keeping a reference to the lowest scoring (best) schedule.
    
    while (best schedule > minimum fitness value)
        foreach schedule s in population of schedules
            foreach time slot
               if (random < .5)
                   choose value from best schedule
               else
                   choose value from schedule s
               end if
           end foreach
           score schedule s with fitness function
        end foreach
    end while
    

    虽然这种方法不会产生最优调度并具有寻找局部最小值的可能性。它总是会产生一个时间表，你可以随时添加更多的约束的健身功能，你不希望看到的任何条件。这种类型的算法可以处理许多不同类型的约束satisifaction问题。

    While this method will not produce an optimal schedule and has the possibility of finding local minimums. It will always produce a schedule and you can always add more constraints to the fitness function for any conditions you don't want to see. This type of algorithm can handle many different types of constraint satisifaction problems.

    我亲自使用类似的算法来安排我的妻子合作社preschool整年在约两个小时我的笔记本电脑。

    I have personally used a similar algorithm to schedule my Wifes Co-Op preschool for the entire year in about two hours on my laptop.

    这篇关于是否有一个调度算法，优化了＆QUOT;制造商的时间表＆QUOT;？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！