← 返回题目列表

AtCoder · asprocon6_a

A. 熔炉调度问题

中文机器翻译题面 查看原题

题目说明

你负责为一组批处理炉制定生产计划。共有 M 台设备、I 种产品和 R 个订单。设备有批容量和停机日;同一种产品在不同设备上的加工时间与电力成本不同;设备从一种产品切换到另一种产品时会产生换型时间和换型成本。

订单给出产品、最早开始时刻、交期、数量、最小批量、毛利和延期参数。订单可以拆分到多个批次和多台可加工设备。请安排加工批次和换型区间,在满足容量、设备日历、加工能力和时间不重叠约束的前提下,使总收益尽可能高。

输入

HEADER M I R BL CL
MACHINE m rq mn md_1 ... md_mn
...(M 行)
BOM i m t ec
...(BL 行)
COMBI m i_prev i_next ct cc
...(CL 行)
ORDER r i e d q qmin pr a
...(R 行)
  • MACHINE 给出设备编号、单批容量和停机日。
  • BOM 表示产品 i 可在设备 m 上加工,加工时间为 t,电力成本为 ec。
  • COMBI 给出设备在两种产品之间切换所需的时间 ct 和成本 cc。
  • ORDER 给出订单编号、产品、最早开始、交期、总量、最小批量、毛利和延期参数。

输出

ORDER r m q t_start t_end
COMBI m t_start t_end

ORDER 表示在设备 m 上为订单 r 安排数量 q 的批次;COMBI 表示换型占用区间。每个订单的批次数量之和必须等于需求量,每批满足最小批量且不超过设备容量。加工和换型不得重叠,不得跨越停机日,不得早于最早开始时刻,并且只能采用输入中存在的加工与换型组合。

评分

评测先检查输出是否合法。合法解的评价由订单毛利减去交期延误罚金、电力成本和换型成本得到;公开检查器以固定基准值加毛利后扣除各项成本。目标是最大化总得分。