两类保密排序问题的算法研究

项目名称： 两类保密排序问题的算法研究

项目编号： No.11526184

项目类型： 专项基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 李好好

作者单位： 浙江财经学院

项目金额： 3万元

中文摘要： 本项目主要研究保密背景下以极小化最大完工时间为目标的同型机排序问题和非同类机排序问题。不同于经典的排序问题，保密排序模型涉及多个单位的加工合作，极具有理论意义与实际背景，而且目前还没有得到有效的研究。本项目将重点针对以上两类保密排序模型，以相应的等价的保密0-1规划模型为基础，设计不同的加密方案，使得合作单位在不泄露各自私密加工信息的前提下共同决策以达到原保密排序问题的最优排序。更进一步，本项目将从规划问题的连续化算法出发，深入分析其特征，尝试探索有效的保密排序问题的组合式算法。

中文关键词： 平行机排序；多方安全计算；保密模型；随机矩阵变换；组合式算法

英文摘要： This project mainly investigate two types of scheduling problems Pm||Cmax and Rm||Cmax which aims to minimize makespan on m identical parallel machines and m unrelated parallel machines in the case of privacy-preserving. In contrast with classical scheduling problems, the parameters in such two scheduling problems 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 first construct secure schemes based on 0-1 programmings such that the optimal solutions to the secure programs are publicly generated and are available to convert into the optimal solutions of the original problems. Then we analyze the characters of the continuous algorithms for privacy-preserving linear programs, and try to design the combinational algorithms for privacy-preserving scheduling problems.

英文关键词： Parallel Machine Scheduling；Multiparty Computation；Privacy-preserving Model；Stochastic Matrix Transformation；Combinational Algorithm