×

zbMATH — the first resource for mathematics

Decentralised scheduling with confidentiality protection. (English) Zbl 1380.90128
Summary: As resources become rare, collaboration is increasingly important for players in a decentralised supply chain. One of the main challenges in collaboration is to find close to globally optimal solutions without sharing individual players’ private data. For problems that are amenable to MILP formulations with a global objective as a sum of linear objective-functions of individual players, we present a Lagrangian relaxation and Secure Sum Protocol based methodology that can find correct global lower- and upper-bounds without needing to share any private data.

MSC:
90B35 Deterministic scheduling theory in operations research
91A12 Cooperative games
91A80 Applications of game theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barahona, F.; Anbil, R., The volume algorithm: producing primal solutions with a subgradient method, Math. Program., 87, 3, 385-399, (2000) · Zbl 0961.90058
[2] Cheng, T. C.E.; Ng, C. T.; Yuan, J. J., Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs, Theoret. Comput. Sci., 362, 273-281, (2006) · Zbl 1100.68007
[3] Chopra, S.; Meindl, P., Supply chain management. strategy, planning, & operation, (2007), Pearson Prentice Hall
[4] Clifton, C.; Kantarcioglu, M.; Vaidya, J.; Lin, X.; Zhu, M., Tools for privacy preserving distributed data mining, SIGKDD Explor., 4, 2, 28-34, (2002)
[5] Confessore, G.; Giordani, S.; Rismondo, S., A market-based multi-agent system model for decentralized multi-project scheduling, Ann. Oper. Res., 150, 1, 115-135, (2006) · Zbl 1144.90377
[6] Demeulemeester, E.; Herroelen, W., Project scheduling: A research handbook, (2002), Kluwer Boston · Zbl 1059.90068
[7] Fisher, M.; Raman, A.; McClelland, A., Rocket science retailing is almost here: are you ready?, Harv. Bus. Rev., 72, 3, 83-93, (1994)
[8] Held, M.; Wolfe, P.; Crowder, H., Validation of subgradient optimization, Math. Program., 6, 62-88, (1974) · Zbl 0284.90057
[9] Heydenreich, B.; Mller, R.; Uetz, M., Mechanism design for decentralized online machine scheduling, Oper. Res., 58, 2, 445-457, (2010) · Zbl 1233.90157
[10] Kaur, A.; Kanda, A.; Deshmukh, S., Supply chain coordination: perspectives, empirical studies and research directions, Int. J. Prod. Econ., 115, 2, 316-335, (2008)
[11] Lu, T. P.; Yih, Y., An agent-based production control framework for multiple-line collaborative manufacturing, Int. J. Prod. Res., 39, 10, 2155-2176, (2001) · Zbl 1060.90596
[12] Neumann, C. S.K.; Zimmermann, J., Project scheduling with time windows and scarce resources, (2003), Springer Berlin · Zbl 1059.90001
[13] Pritsker, A.; Watters, L.; Wolfe, P., Multi-project scheduling with limited resources: a zero-one programming approach, Manage. Sci., 16, 93-108, (1969)
[14] Ramdas, K.; Spekman, R., Chain or shackles: understanding what drives supplychain performance, Interfaces, 30, 4, 3-21, (2000)
[15] M. Shackelford, D. Corne, Collaborative evolutionary multi-project resource scheduling, in: Proc. of 2001 Congress on Evolutionary Computation, Vol. 2, 2001.
[16] Simatupang, T.; Sridharan, R., The collaborative supply chain, Int. J. Logist. Manage., 13, 1, 15-30, (2002)
[17] Singh, G.; Ernst, A., Resource constraint scheduling with a fractional shared resource, Oper. Res. Lett., 39, 5, 363-368, (2011) · Zbl 1235.90067
[18] Singh, G.; Weiskircher, R., Collaborative resource constraint scheduling with a fractional shared resource, (Proceedings of 2008 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT-08, (2008), IEEE Computer Society Sydney, Australia), 359-365
[19] Singh, G.; Weiskircher, R., A multi-agent system for decentralised fractional shared resource constraint scheduling, Web Intell. Agent Syst., 9, 2, 99-108, (2011)
[20] Wellman, M.; Walsh, W.; Wurman, P.; MacKie-Mason, J., Auction protocols for decentralized scheduling, Games Econom. Behav., 35, 271-303, (2001) · Zbl 0996.90047
[21] Yao, A., How to generate and exchange secrets, (Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, (1986), IEEE), 162-167
[22] S. Zhang, F. Makedon, Privacy preserving learning in negotiation, in: Proceedings of the 2005 ACM symposium on Applied computing, SAC’05, 2005, pp. 821-825.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.