排序问题的词语属性

排序问题的百科含义

排序问题(sequencing problem)亦称工件加工日程表问题，是一类典型的组合优化问题。设用m台机器加工n个工件，给定了加工每个工件所用机器的次序，以及每台机器加工每个工件所需要的时间、问题是确定工件在每台机器上的加工次序以使预先选定的目标函数达到最小，这个目标函数通常是完成时间、平均完成时间、机器的空间时间等的一个非降函数。排序问题有两个类型：1.流水作业，这时要求每个工作在机器上的加工次序都一样；2.工件作业，这时每个工件在机器上的加工次序不必一致。流水作业可以看做是工件作业的一种特殊情形，三台或以上机器的排序问题多为NP完全问题.因此是很困难的。