单机调度

What · 是什么

单机调度（scheduling on one machine）问题：n 个作业在一台机器上依次加工，作业 i 耗时 t_i，若作业在等待 t 秒后才被处理则需付罚金 f_i(t)。目标是最小化总罚金 F(π)=Σ f_πi(等待时间)。特殊情形可精确求解：①线性罚函数 f_i(t)=c_i·t：按 c_i/t_i 非增排序（交换相邻两项分析最优条件）；②指数罚函数 f_i(t)=c_i·e^(αt)：按 (1−e^(αt_i))/c_i 非增排序；③相同单调增罚函数：按 t_i 非降排序。Livshits–Kladov 定理：排列法（交换相邻作业看罚金变化）仅适用于上述三类罚函数。若目标改为'最小化最大延迟'，则按截止期 d_i 非降排序（EDD 规则）贪心。

Why · 为什么

How · 实现

伪代码

# 线性罚函数 f_i(t)=c_i*t, 最小化总罚金
sort jobs by (c_i / t_i) 降序   # 或按 c_i*t_j > c_j*t_i 比较器

# 相同单调罚函数(如均方差/总完成时间) => 按 t_i 升序 (SPT)
# 指数罚函数 => 按 (1-exp(a*t_i))/c_i 降序

# 最小化最大延迟 => 按 deadline d_i 升序 (EDD)

Python 实现

def schedule_linear(jobs):
    """单机+线性罚金 f_i(t)=c_i*t: 按 c/t 降序排.
    jobs: list of (t_i, c_i). 返回最优顺序列表.
    """
    return sorted(range(len(jobs)), key=lambda i: jobs[i][1] / jobs[i][0], reverse=True)


def total_penalty(jobs, order):
    """给定顺序的总罚金 (线性情形): sum c_i * (等待时间)"""
    time = 0
    total = 0
    for i in order:
        t, c = jobs[i]
        total += c * time
        time += t
    return total


def schedule_edd(jobs):
    """最小化最大延迟: EDD 按截止期升序.
    jobs: list of (duration, deadline). 返回顺序.
    """
    return sorted(range(len(jobs)), key=lambda i: jobs[i][1])


def max_lateness(jobs, order):
    """最大延迟 L_max = max(completion - deadline)"""
    time = 0
    L = 0
    for i in order:
        dur, ddl = jobs[i]
        time += dur
        L = max(L, time - ddl)
    return L


if __name__ == "__main__":
    # 线性罚金: 对拍暴力
    import itertools

    def brute_linear(jobs):
        return min(itertools.permutations(range(len(jobs))),
                   key=lambda o: total_penalty(jobs, o))

    jobs1 = [(2, 3), (3, 1), (1, 5), (4, 2)]
    ord1 = schedule_linear(jobs1)
    assert total_penalty(jobs1, ord1) == total_penalty(jobs1, brute_linear(jobs1))

    for _ in range(200):
        import random
        random.seed(0)
        n = random.randrange(1, 8)
        js = [(random.randrange(1, 8), random.randrange(1, 8)) for _ in range(n)]
        o = schedule_linear(js)
        assert total_penalty(js, o) == total_penalty(js, brute_linear(js)), js

    # EDD 最小化最大延迟: 对拍暴力
    def brute_edd(jobs):
        return min(itertools.permutations(range(len(jobs))),
                   key=lambda o: max_lateness(jobs, o))

    jobs2 = [(3, 6), (2, 5), (4, 9), (1, 2)]
    o2 = schedule_edd(jobs2)
    assert max_lateness(jobs2, o2) == max_lateness(jobs2, brute_edd(jobs2))

    for _ in range(200):
        n = random.randrange(1, 8)
        js = [(random.randrange(1, 8), random.randrange(1, 15)) for _ in range(n)]
        o = schedule_edd(js)
        assert max_lateness(js, o) == max_lateness(js, brute_edd(js)), js

    print("schedule-one-machine tests passed")

易错点

• 不同目标函数对应不同排序规则：线性罚金 c/t、EDD 用于最大延迟、SPT 用于总完成时间，勿混用
• 浮点除法排序在大数据下精度问题，改用交叉乘法比较
• 带常数项罚金（f_i(t)=c_i·t+d_i）先把常数项单独求和
• 作业可能被'可中断/抢占'模型改变结果
• 相邻交换法只在满足 Livshits–Kladov 前提时适用

例题

信源

• CP-Algorithms✓ https://cp-algorithms.com/schedules/schedule_one_machine.html
• Wikipedia✓ https://en.wikipedia.org/wiki/Job_shop_scheduling