| 查看: 1462 | 回复: 5 | |||
[求助]
[求助] 一个非典型的排序问题
|
|
小弟非数学专业，遇到一个非典型的排序问题，之前也没有接触过太多排序论的知识，故希望各位虫友能帮忙解答。 首先有2个机器，N个工件，每个工件都要在这两个机器上加工。给定每个工件在两个机器上的加工时间P_{in} ，n表示工件个数，i表示机器个数。 和一般的工件加工不一样，这里两个机器可以同时加工一个工件，而我希望找到一个排序（这个顺序在两个机器上是相同的），使得在最短的完工时间内，每个工件在两个机器上的加工时间之和最短。 T_{in}^{1}是任务P_{in} 在i机器上的开始时间，T_{in}^{2} 是任务P_{in} 在i机器上的结束时间。 这个问题的数学表示如下，其中max(T_{1n}^{2},T_{2n}^{2})-min(T_{1n}^{1},T_{2n}^{1}) 表示的就是每个工件的在线加工时间。 求一个排序σ，使得min\sum_{n=1}^{N}[max(T_{1n}^{2},T_{2n}^{2})-min(T_{1n}^{1},T_{2n}^{1})] ， 其中： T_{in}^{2} - T_{in}^{1} = P_{in} \underset{1\leq n\leq N}{MAX}(T_{in}^{2})=\sum_{n=1}^{N}P_{in} 其中i=1，2； \forall k (1\leq k\leq N-1),T_{i\sigma (k)}^{2}= T_{i\sigma (k+1)}^{1} 而我的疑惑是，如何证明这个问题是否是一个NP问题（我个人直观认为是NP问题），如果是，最好能给出证明方法；如果不是，则最好能给出最优方法。 您的任何一个建议都不甚感激！ |
回复此楼» 猜你喜欢
材料类284调剂
已经有46人回复
-
本人女孩
已经有3人回复
-
一志愿211，化学310分，本科重点双非，求调剂
已经有22人回复
-
广东省 085601 329分求调剂
已经有11人回复
-
277 数一104，学硕，求调剂
已经有18人回复
-
085600材料与化工329分求调剂
已经有5人回复
-
286求调剂
已经有8人回复
-
调剂
已经有13人回复
-
080500求调剂
已经有16人回复
-
272分材料子求调剂
已经有34人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 发表SCI，作者排序问题
已经有53人回复
- 关于参考文献中第一作者和通讯作者的排序问题
已经有3人回复
- 关于评审意见的排序问题
已经有3人回复
- 关于工作基础的作者排序问题
已经有28人回复
- 青基人员排序问题
已经有16人回复
- 【原创】求助博士期间文章发表作者排序问题
已经有32人回复
- endnote排序混乱问题
已经有9人回复
- 关于正交表的某一因素的水平排序问题
已经有3人回复
- 转帖 数量关系中排列组合问题的七大解题策略
已经有6人回复
| 公式看不太清楚，我传附件里。。。 |
» 本帖附件资源列表
-
欢迎监督和反馈：小木虫仅提供交流平台，不对该内容负责。
本内容由用户自主发布，如果其内容涉及到知识产权问题，其责任在于用户本人，如对版权有异议，请联系邮箱：xiaomuchong@tal.com - 附件 1 : 一个非典型的排序问题.docx
2012-05-01 22:58:45, 27.99 K
2楼2012-05-01 22:58:47
3楼2012-05-02 10:56:09
4楼2012-05-02 12:46:28
liuhl2012
木虫 (职业作家)
- 应助: 31 (小学生)
- 金币: 2604.5
- 散金: 10
- 红花: 3
- 沙发: 1
- 帖子: 3090
- 在线: 70.1小时
- 虫号: 1795435
- 注册: 2012-05-04
- 专业: 通信理论与系统
5楼2012-05-05 10:45:24
6楼2012-05-06 15:54:33
5