非同类机极小化最大完工时间的保密排序问题

Privacy-preserving scheduling model for minimizingthe makespan on unrelated parallel machines

提出并研究了一类非同类机的极小化最大完工时间的保密排序问题Rm||Cmax.该问题的模型参数分为若干组,每个组都由一个不愿意共享或公开自己数据的单位所拥有.基于随机矩阵变换构造了一个不泄露私有数据且与原问题等价的安全规划模型,求解该安全模型可以获得问题的最优解,而且各单位的隐私数据仍然保持不被泄露.

In this paper the scheduling problem Rm||Cmax is cast in a privacy-preserving framework.Consider the situation that the parameters in problem Rm||Cmax are partitioned into groups.Each group is owned by a distinct private entity that is unwilling to share or make public its own data.We construct a secure program based on the privately held data without revealing it by employing random matrix transformation.The secure program has the same optimal minimum value as the original mixed 0-1 linear program model of the problem Rm||Cmax,and the optimal solution to the secure program is publicly generated and is available to all entities.The 0-1 components in optimal solution to the secure program are coincident to those in optimal solution to the original solution.