Optimal Timetable Formation Problem

AUTHOR(S)

Anil Kumar S

DOI: https://doi.org/10.46647/ijetms.2023.v07i04.016

ABSTRACT
We consider the following problem. Given a set of m agents and n time slots for performing jobs such that agent i has a preference value of pij on slot j for each i and j. Our task is to find an optimal time table which maximises the minimum total preferences of all the agents, thereby ensuring the maximum fairness in the time slot allocation among the agents. We show that this problem is NP -complete and has a polynomial time randomised algorithm that computes the optimal solution of the problem with very high probability that every time slot has been allocated to at most agent and every agent receives time slot bundles of optimum size. The crux of our solution relies on solving two linear programs namely Slot Allocation LP and Slot Bundle LP followed by a rondomised slot allocation which ensures the high probability of the method in getting the optimal solution.
Page No: 83 - 89

References:

Nikhil Bansal and Maxim Sviridenko. The santa claus problem. In Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC ’06, pages 31–40, New York, NY, USA, 2006. ACM.

Arash Asadpour, Uriel Feige, and Amin Saberi. Santa claus meets hypergraph matchings. ACM Trans. Algorithms, 8(3):24:1–24:9, July 2012.

Sami Davies, Thomas Rothvoss, and Yihao Zhang. A tale of santa claus, hypergraphs and matroids. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Mathematics

George B Dantzig. Origins of the simplex method. In A history of scientific computing, pages 141–151. 1990.

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022.

Annamalai Chidambaram, Christos Kalaitzis, and Ola Svensson. ACM Trans. Algorithms, 13(3):37:1–37:28, May 2017.

Shoeb Ahmed Syed; Steve Ales; Rajesh Kumar Behera; Kamalakanta Muduli. "Challenges, Opportunities and Analysis of the Machining Characteristics in hybrid Aluminium Composites (Al6061-SiC-Al2O3 ) Produced by Stir Casting Method". International Research Journal on Advanced Science Hub, 4, 08, 2022, 205-216. doi: 10.47392/irjash.2022.051

Ashima Saxena; Preeti Chawla. "A Study on the Role of Demographic Variables on Online Payment in Delhi NCR". International Research Journal on Advanced Science Hub, 4, 08, 2022, 217-221. doi: 10.47392/irjash.2022.052

M. S. N. K. Nijamudeen, G. Muthuarasu, G. Gokulkumar, A. Nagarjunan, and T. Pravin, “Investigation on mechanical properties of aluminium with copper and silicon carbide using powder metallurgy technique,” Advances in Natural and Applied Sciences, vol. 11, no. 4, pp. 277–280, 2017.

R. Devi Priya, R. Sivaraj, Ajith Abraham, T. Pravin, P. Sivasankar and N. Anitha. "MultiObjective Particle Swarm Optimization Based Preprocessing of Multi-Class Extremely Imbalanced Datasets". International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems Vol. 30, No. 05, pp. 735-755 (2022). Doi: 10.1142/S0218488522500209

Pravin T, M. Subramanian, R. Ranjith, Clarifying the phenomenon of Ultrasonic Assisted Electric discharge machining, “Journal of the Indian Chemical Society”, Volume 99, Issue 10, 2022, 100705, ISSN 0019-4522, Doi: 10.1016/j.jics.2022.100705

T. Pravin, C. Somu, R. Rajavel, M. Subramanian, P. Prince Reynold, Integrated Taguchi cum grey relational experimental analysis technique (GREAT) for optimization and material characterization of FSP surface composites on AA6061 aluminium alloys, Materials Today: Proceedings, Volume 33, Part 8, 2020, Pages 5156-5161, ISSN 2214-7853, https://doi.org/10.1016/j.matpr.2020.02.863.

V.S. Rajashekhar; T. Pravin; K. Thiruppathi , “Control of a snake robot with 3R joint mechanism”, International Journal of Mechanisms and Robotic Systems (IJMRS), Vol. 4, No. 3, 2018. Doi: 10.1504/IJMRS.2018.10017186

Minh Ly Duc; Que Nguyen Kieu Viet. "Analysis Affect Factors of Smart Meter A PLS-SEM Neural Network". International Research Journal on Advanced Science Hub, 4, 12, 2022, 288-301. doi: 10.47392/irjash.2022.071

Lely Novia; Muhammad Basri Wello. "Analysis of Interpersonal Skill Learning Outcomes in Business English Students Class". International Research Journal on Advanced Science Hub, 4, 12, 2022, 302-305. doi: 10.47392/irjash.2022.072

Ms. Nikita; Sandeep Kumar; Prabhakar Agarwal; Manisha Bharti. "Comparison of multi-class motor imagery classification methods for EEG signals". International Research Journal on Advanced Science Hub, 4, 12, 2022, 306-311. doi: 10.47392/irjash.2022.073

Aniket Manash; Ratan Kumar; Rakesh Kumar; Pandey S C; Saurabh Kumar. "Elastic properties of ferrite nanomaterials: A compilation and a review". International Research Journal on Advanced Science Hub, 4, 12, 2022, 312-317. doi: 10.47392/irjash.2022.074

Prabin Kumar; Rahul Kumar; Ragul Kumar; Vivek Rai; Aniket Manash. "A Review on coating of steel with nanocomposite for industrial applications". International Research Journal on Advanced Science Hub, 4, 12, 2022, 318-323. doi: 10.47392/irjash.2022.075

Twinkle Beniwal; Vidhu K. Mathur. "Cloud Kitchens and its impact on the restaurant industry". International Research Journal on Advanced Science Hub, 4, 12, 2022, 324-335. doi: 10.47392/irjash.2022.076

Pradeep Kumar Krishnan; Mallak Al Maqbali. "Investigating the Viscosity Reduction of Heavy Crude Oil Using Organic Materials to Improve Oil Production and Transportation". International Research Journal on Advanced Science Hub, 4, 01, 2022, 1-6. doi: 10.47392/irjash.2022.001

Rajdeep Routh; Dhruma Bhavsar; Rajiv Patel. "Socio-Economic and Policy Impacts of Heritage Conservation: A Case of Deewanji ni Haveli, Ahmedabad". International Research Journal on Advanced Science Hub, 4, 01, 2022, 7-15. doi: 10.47392/irjash.2022.002

Manoj Kumar Baral; Radhakrishna Das; Abhipsa Sahu. "DFIG based WT harmonics Analysis subjected to Diverse Transmission Fault". International Research Journal on Advanced Science Hub, 4, 01, 2022, 16-23. doi: 10.47392/irjash.2022.003

Khaled Salem Ahmad Amayreh; Ahmad Taufik Hidayah Bin Abdullah. "Conjunction in Expository Essay Writing by Jordanian Undergraduate Students Studying English as a Foreign Language (EFL)". International Research Journal on Advanced Science Hub, 4, 02, 2022, 24-30. doi: 10.47392/irjash.2022.006

Mohammadibrahim Korti; Basavaraj S. Malapur; Smita Gour; Rajesh M. Biradar. "Shuchi 1.0: Robotic System For Automatic Segregation of Waste & Floor Cleaning". International Research Journal on Advanced Science Hub, 4, 02, 2022, 31-37. doi: 10.47392/irjash.2022.007

Bhuneshwari Nayak; Rachana Choudhary; Roymon M. G.. "Isolation, Screening and Morphological characterization of Laccase producing fungi". International Research Journal on Advanced Science Hub, 4, 02, 2022, 38-43. doi: 10.47392/irjash.2022.008

Kotte Sowjanya; Munazzar Ajreen; Paka Sidharth; Kakara Sriharsha; Lade Aishwarya Rao. "Fuzzy thresholding technique for multiregion picture division". International Research Journal on Advanced Science Hub, 4, 03, 2022, 44-50. doi: 10.47392/irjash.2022.011

Mohammadibrahim Korti; Girish B. Shettar; Ganga A Hadagali; Shashidhar Shettar; Shailesh Shettar. "Voice-based direction control of a robotic vehicle through User commands". International Research Journal on Advanced Science Hub, 4, 03, 2022, 51-56. doi: 10.47392/irjash.2022.012

Nagendra Singh; Manoj Kumar Agrawal; Sanjeev Kumar Verma; Ashish Kumar Tiwari. "A Review on Effect of Stress and Strain Distribution on the AA5083 With Respect to Different Channel Angle of ECAP". International Research Journal on Advanced Science Hub, 4, 03, 2022, 57-66. doi: 10.47392/irjash.2022.013

Nusrath Unnisa A; Manjula Yerva; Kurian M Z. "Review on Intrusion Detection System (IDS) for Network Security using Machine Learning Algorithms". International Research Journal on Advanced Science Hub, 4, 03, 2022, 67-74. doi: 10.47392/irjash.2022.014

Jyotshana Upadhyay. "Digital Marketing Practices Adoption in Micro, Small and Medium Businesses for Inclusive Growth". International Research Journal on Advanced Science Hub, 4, 04, 2022, 75-80. doi: 10.47392/irjash.2022.021

Arti Maurya; Kartick Chandra Majhi; Mahendra Yadav. "One Pot Synthesis of Lanthanum Doped Cobalt Selenate Electrocatalyst for Oxygen Evolution Reaction (OER)". International Research Journal on Advanced Science Hub, 4, 04, 2022, 81-87. doi: 10.47392/irjash.2022.022

Palash Mondal; Hrittik Dey; Sreetama Paul; Shamik Sarkar; Apurba Das; Amit Karmakar. "Additively manufactured porous titanium alloy scaffolds for orthopaedics: An effect of process parameters on porosity". International Research Journal on Advanced Science Hub, 4, 04, 2022, 88-93. doi: 10.47392/irjash.2022.023

Kousik Bhattacharya; Avijit Kumar Chaudhuri; Anirban Das; Dilip K. Banerjee. "A Data Mining based study on Dengue Fever: A Review". International Research Journal on Advanced Science Hub, 4, 04, 2022, 101-107. doi: 10.47392/irjash.2022.025

Bharathi M; Senthil Kumaran S; Edwin Samson P. "Influence of Nano Silica Particles on Quasistatic Mechanical and Low Velocity Impact Properties of Carbon-Glass-Sunn Hemp/Epoxy in Intra-Inter Ply Hybrid Composites". International Research Journal on Advanced Science Hub, 4, 05, 2022, 120-133. doi: 10.47392/irjash.2022.032

Anukriti Sharma; Navdeep Singh. "Hybrid Modulation for Reduced Switches AC-AC Multi Frequency Converter". International Research Journal on Advanced Science Hub, 4, 05, 2022, 134-142. doi: 10.47392/irjash.2022.033

Kousik Bhattacharya; Avijit Kumar Chaudhuri; Anirban Das; Dilip K. Banerjee. "Comparison of Recent Data Mining Algorithms to Identify of the factors and effects of Dengue Fever and Ensemble Random Forest, A new Algorithm". International Research Journal on Advanced Science Hub, 4, 05, 2022, 143-153. doi: 10.47392/irjash.2022.034

Ch Yashwanth Krishna; Y Shanmukha Venkata Sri Sai; Muniyandy Elangovan. "Development of Telemetry system for Student Formula Cars and All-terrain vehicles". International Research Journal on Advanced Science Hub, 4, 05, 2022, 154-160. doi: 10.47392/irjash.2022.035

Thenmozhi S; Praveen A; Subhavarman S; Jaipriya S; Malathy S. "QoS based Prioritization using Shortest Path and Hamming Residue Method". International Research Journal on Advanced Science Hub, 4, 05, 2022, 161-167. doi: 10.47392/irjash.2022.036

Ms. Ritu; Preeti Chawla. "Factor Affecting User Acceptance for Digital Wallets: A Developing Country’s Perspective". International Research Journal on Advanced Science Hub, 4, 06, 2022, 168-174. doi: 10.47392/irjash.2022.041

Jagandas S.; Mallikarjuna Rao G; Hitesh Kumar M; Srujan Kumar T. "A Scientometric Review of Na2SiO3/NaOH Versus SiO2/Na2O is above 2.85:1 Alkaline solution Activated Geopolymer Concrete". International Research Journal on Advanced Science Hub, 4, 06, 2022, 175-179. doi: 10.47392/irjash.2022.042

Muniyandy Elangovan; Mohammed Nayeem; Mohamed Yousuf; Mohamed Nauman. "Energy opportunities for delivery robot during Disaster". International Research Journal on Advanced Science Hub, 4, 06, 2022, 180-185. doi: 10.47392/irjash.2022.043

Nagendra Singh; Manoj Kumar Agrawal; Sanjeev Kumar Verma; Ashish Kumar Tiwari. "Study of the effect of ECAPed Method on the Mechanical Properties of AA 5083: An Overview". International Research Journal on Advanced Science Hub, 4, 06, 2022, 186-191. doi: 10.47392/irjash.2022.044

Muniyandy Elangovan; Mohamed Yousuf; Mohamed Nauman; Mohammed Nayeem. "Design and Development of Delivery Robot for Commercial Purpose". International Research Journal on Advanced Science Hub, 4, 07, 2022, 192-197. doi: 10.47392/irjash.2022.047

Manikandan N; Swaminathan G; Dinesh J; Manish Kumar S; Kishore T; Vignesh R. "Significant Attention in Industry and Academia for Wire Arc Additive Manufacturing (WAAM) - A Review". International Research Journal on Advanced Science Hub, 4, 07, 2022, 198-204. doi: 10.47392/irjash.2022.048

How to Cite This Article:
Anil Kumar S . ijetms;7(4):83-89. DOI: 10.46647/ijetms.2023.v07i04.016