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

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.

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

本项目主要研究以极小化最大完工时间为目标的保密同型机和保密非同类机排序问题。通过建立等价的0-1线性规划模型，利用矩阵分块和随机矩阵变换，设计对应排序问题的保密方案。同时，探讨了同为涉及多方合作的一类排序问题：可转包两台流水作业机排序的组合式算法设计。此外，利用共通的矩阵变换技巧，研究了不确定型规划模型若干类型的最优解及最优值的结构及性质。