Open Access Open Access  Restricted Access Subscription or Fee Access

Equitable Payment Distribution for Project-Expert Scheduling using Genetic Algorithm

Sandeep R. Vasant, Avani R. Vasant, Dr.N.N. Jani, Swapnil S. Marathe

Abstract


The human race is facing a large number of very complex real-world problems. One of them is a very common and typical problem faced by many large organizations executing multiple projects concurrently. They have a huge pool of similarly skilled human resource (experts) which needs to be allocated to multiple projects with different units of work and different payment rates such that each expert gets an equitable payment. The above problem is an allocation problem and it falls into the category of NP Hard problems. A simple and obvious approach could be application of Round robin technique to this problem. However, this technique is not suitable and has a set of limitations [1]. As per [6] no polynomial-time algorithm exists to solve this problem optimally. In this paper we have introduced a novel Genetic Algorithm based approach with problem specific three-dimensional representation scheme to find the optimal solution for the equitable payment distribution. We have implemented an algorithm that achieves average performance which is close to the optimal across many experimental scenarios. Furthermore, this evolutionary algorithm does not require special high powered computing hardware and is still quite efficient. This makes it ideally suitable for solving this type of allocation problems.

Keywords


Project, Experts, NP (Non Polynomial), Round Robin, Genetic Algorithm, Exhaustive Search, Elitism, Crossover, Muatation

Full Text:

PDF

References


S. Vasant, A. Vasant, N N Jani, A Novel Proposed Approach for an Equitable Payment Distribution using Genetic Algorithm, IEEE Xplore CSNT (2012), Pages 841-851.

M. Mitchell, Introduction to Genetic Algorithms, Cambridge: MIT Press, 1996

What are Genetic Algorithms? – Trading Solutions.

Allocating hard real-time tasks: An NP-Hard problem made easy, K. W. Tindell, A. Burns and A. J. Wellings.

Exhaustive Search, Combinatorial Optimization and Enumeration: Exploring the Potential of Raw Computing Power by Jurg Nievergelt.

S. Vasant, Dr. N N Jani,: Optimizing travelling salesman problem using genetic algorithm, Proceeding of ICISET-2011, Rajkot .

Mohammed Anayet, Ullah Patwari, A.K.M. Nurul Amin: Artificial Intelligence Model of Surface Roughness for End Milling Operation of Steel and its Verification by Genetic Algorithm, Applied Mechanics and materials.

S. Elangovan, K. Anand and K. Prakasan: Parametric optimization of ultrasonic metal welding using response surface methodology and genetic algorithm, springer.

Sanjaya Kumar Panda, Sourav Kumar Bhoi : An Effective Round Robin Algorithm using Min-Max Dispersion Measure, International journal on Computer Science and Engineering.

Husbands, P. (1996). “Genetic Algorithms for Scheduling” AISB Quarterly, No 89

A.T. Ernst et al. / European Journal of Operational Research 153 (2004) 3–27

M.Garey and D.Johnson Computers and Intractability: a guide to the theory of NP-Completeness W.H.Freeman, New York 1979

NMG, M.E. Thesis, GCET; vvnagar-2004

K. Sycra, S. Roth , M. Fox, Resource allocation in distributed factory scheduling, IEEE Expert, pages 29-40, Feb.1991

Jensen, M.T. 2003. Generating Robust and Flexible Job Shop Schedules Using Genetic Algorithms. J. IEEE Transactions on Evolutionary Computation. 7, 275-288.

Andrew J. Page, Thomas J. Naughton, Dynamic task scheduling using genetic algorithms for heterogeneous distributed computing. Proceeding IPDPS '05 Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 6 - Volume 07 Page 189.1

Tom V Mathew, Snehamay Khasnabis, Sabyasachee Mishra, Optimal resource allocation among transit agencies for fleet management, Transportation Research Part A: Policy and Practice, Volume 44, Issue 6, July 2010, Pages 418–432

Wei lo, Yih - Tzoo Chen, Optimization of Contractors S-Curve using Genetic Algorithms, 24th International Symposium on Automation & Robotics in construction (ISARC 2007), IIT Madras.

Hegazy, T. (1999), Optimization of resource allocation and leveling using Genetic Algorithms, Journal of Construction of Engineering and Management, 125(3), page 167-175.

EASA, S M. (1989), Resource leveling in construction by optimization, Journal of Construction of Engineering and Management, 115(2), page 302-316.

Leu, S S and Hung, T. H. (2002), A genetic algorithm based optimal resource constrained scheduling simulation model, Journal of construction Management and Economics, 20, page 131-141.

Senouci, A. B., Adeli, H. (2001), Resource scheduling using neural dynamics model, Journal of Construction of Engineering and Management, 127(1), page 28-34.

D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, Massachusetts, 1989.

H. Kasahara and S.Narita. Practical multiprocessing scheduling algorithms for efficient parallel processing. IEEE Transactions on Computers, 33(11):1023–1029, November 1984.

J. H. Holland. Adaptation in Natural and Artificial Systems. MIT Press, Cambridge, MA, USA, 1992.


Refbacks

  • There are currently no refbacks.