摘要
研究工件带就绪时间的单机供应链排序问题, 即工件到达后按何种顺序在机器上加工, 并将完工工件如何由运输工具发送给客户,使得生产费用与发送费用总和最少. 这里, 每个工件的生产费用为工件的发送时刻, 多个工件可组成一批一次发送给客户, 发送费用与发送次数成正比. 对于工件允许中断加工的问题, 基于SRPT规则给出多项式时间的动态规划算法求解最优序;对于工件不允许中断加工的问题, 证明问题是强NP难的, 并提出了性能比为的近似算法.
Abstract
This paper is concerned with the supply chain scheduling problem integrated production and distribution operations. Each job is first processed on a single machine, then is delivered to the customer directly by one vehicle available, with other jobs as one shipment. The objective is to minimize the total cost including production cost and distribution cost in the processing stage and the delivering stage. Production cost of every job is measured by the time when the job is delivered to the customer in a shipment. The distribution costs are proportional to the delivery times. If jobs can be suspended during processing stage, it can be solved by dynamic programming polynomially based on SRPT rule. If jobs are not permitted to be suspended, the problem is strongly NP-hard, and an approximation algorithm with the worst performance is presented.
关键词
应链排序 /
SRPT规则 /
动态规划 /
强NP难
{{custom_keyword}} /
范静.
工件带就绪时间的单机供应链排序问题. 系统科学与数学, 2011, 31(11): 1439-1443. https://doi.org/10.12341/jssms11740
FAN Jing.
SUPPLY CHAIN SCHEDULING WITH JOBS' RELEASE TIMES A SINGLE MACHINE. Journal of Systems Science and Mathematical Sciences, 2011, 31(11): 1439-1443 https://doi.org/10.12341/jssms11740
中图分类号:
90B35
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}