Solving Job Shop Scheduling Problem Based on Employee Availability Constraint

Solving Job Shop Scheduling Problem Based on Employee Availability Constraint G. Ramya Sathyabama University M. Chandrasekaran Vel’s University
Manufacturing System is enabled with an excellent knowledge on production plan, proper scheduling of machinery process, employee timetabling and labor costs. Heuristic algorithms are developed to bring optimized results in stipulated time with respect to optimum schedule. This article deals with minimizing the maximum completion time (makespan) based on job scheduling and minimization of labor costs based on employee workload with Shuffled Frog Leaping Algorithm and Sheep Flock Heredity Model Algorithm. The labor costs minimization and makespan which is to find a schedule that satisfies the organizations rules, employees preferences, due date and customers. The formulation of assigning workload for employees is concerned with assigning number of employees into a given set of shifts over a fixed period of time and week task. The main problem attempts to minimize labor costs based on performance criteria and assigning the loads equally among all employees. Several local search methods and heuristics algorithms has been proposed in many research on Job shop scheduling. The Results are compared with other heuristics in terms of makespan, idle time and Labor costs the Shuffled Frog Leaping algorithm performs result oriented than other Heuristics Algorithm.
8 2013 197 206 https://www.scientific.net/PolicyAndEthics/PublishingPolicies https://www.scientific.net/license/TDM_Licenser.pdf 10.4028/www.scientific.net/AMM.376.197 https://www.scientific.net/AMM.376.197 https://www.scientific.net/AMM.376.197.pdf Yarong Chen, Zailin Guan & Xinyu shao, A Comparative Analysis of job Shop Scheduling Algorithms, MSIE (2011) – IEEE transactions 978-1-4244-8385, Pg. No. 1091-1095. 10.1109/msie.2011.5707607 Ahmed S. Ghoniem, Static and dynamic job-shop scheduling using rollinghorizon approaches and the Shifting Bottleneck Procedure , Thesis, Master of Science In Industrial and Systems Engineering (2002). Mattfeld, D.C., Bierwirth, C., and Kopfer, H., (1998), A Search Space Analysis of the Job Shop Scheduling Problem, to appear in Annals of Operations Research. Shmoys, D. B., Stein, C., and Wein, J., (1994), Improved Approximation Algorithms for Job shop Scheduling Problems, SIAM Journal of Computer science, June, 23(3), pp.617-632. 10.1137/s009753979222676x French, S., (1982), Sequencing and Scheduling - An Introduction to the Mathematics of the Job- Shop, Ellis Horwood, John-Wiley & Sons, New York. 10.1287/opre.8.2.219 Manne, A. S., (1960), On the Job-Shop Scheduling Problem, Operations Research, vol 8, pp.219-223. Blazewicz, J., Dror, M., and Weglarz, J., (1991), Mathematical Programming Formulations for Machine Scheduling: A Survey, European Journal of Operational Research, 51(3), pp.283-300. 10.1016/0377-2217(91)90304-e Eusuff M, Lansey K, Pasha F (2006) Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization. Eng Optim 38: 129–154. 10.1080/03052150500384759 Mohammadreza Farahani, Saber Bayat Movahhed, Seyyed Farid Ghaderi1 , A hybrid meta- heuristic optimization algorithm based on SFLA. 2nd International Conference on Engineering Optimization September 6 - 9, 2010, Lisbon, Portugal. M. Eusuff, K. E. Lansey, Optimization of water distribution network design using the shuffled frog leaping algorithm, Journal of Water Resource Planning and Management, vol. 129, issue 3, 210-225, (2003). 10.1061/(asce)0733-9496(2003)129:3(210) Emad Elbeltagi , Tarek Hegazyz and Donald Griersonmad (2007), A modified shuffled frog- leaping optimization algorithm applications to project management, Structure and Infrastructure Engineering, Vol. 3, No. 1, March 2007, 53 – 60. 10.1080/15732470500254535 Quan-Ke Pan & Ling Wang & Liang Gao & Junqing Li, An effective shuffled frog-leaping algorithm for lot-streaming flow shop scheduling problem. Int J Adv Manufacturing Technology, DOI 10. 1007/s00170-010-2775-3. 10.1007/s00170-010-2775-3 M. Alinia Ahandani, N. Pourqorban Shirjoposht & R. Banimahd , Job-Shop Scheduling Using Hybrid Shuffled Frog Leaping, online. 10.1109/csicc.2009.5349656 M. Chandrasekaran, P. Asokan, S. Kumanan, Multi objective optimization for job shop scheduling problems using Sheep Flocks Heredity Modal Algorithm, Int J Mfg Sci and Tech, Vol 9, 2: 47-54, (2007). Chandramouli, Anandaramam An Improved Sheep Flock Heredity Algorithm for Job Shop Scheduling, International Journal of Industrial Engineering Computation 2 (2011), Pg. Np. 749-764. 10.5267/j.ijiec.2011.06.007 M. Eusuff, K. Lansey, F. Pasha, Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization,. Eng Optima 38: 129–154, (2006). 10.1080/03052150500384759 Emad Elbeltagia, Tarek Hegazy and Donald Grierson, Comparison among five evolutionary-based optimization algorithms, Advanced Engineering Infomatics 19 (2005), 43-53. 10.1016/j.aei.2005.01.004 Amnon Meisels and Andrea Schaerf , Modelling and solving employee timetabling problems, Annals of Mathematics and Artificial Intelligence 39: 41–59, Kluwer Academic Publishers. Printed in the Netherlands, (2003). 10.1023/a:1024460714760 Christian Artigues et. Al. Solving an Integrated employee timetabling and Job shop scheduling problem via hybrid branch and bound , Computers & Operations Research (2009), Pg. No. 2330 –2340. 10.1016/j.cor.2008.08.013 A.T. Ernst et al. Staff scheduling and roistering: A review of applications, methods and models, European Journal of Operational Research, 153 3–27, (2004). Elanz Baghal, Azardoost, A hybrid algorithm for multi objective flexible Job Shop Scheduling Problem, Proceedings of the 2011 International conference on Industrial Engg. & operational Management. Liang Sun et. al, Solving Job Shop Scheduling problem using genetic algorithm with penalty function, International Journal of Intelligent information processing, Vol. no. 2, Dec- (2010). 10.4156/ijiip.vol1.issue2.7 Ren Qing et. al, An Improved genetic algorithm for Job Shop Scheduling Problem, International Conference publications on Computational Intelligence Security (2010), Pg. No. 113 – 116. 10.1109/cis.2010.32 Christian Artigues et. Al., A Flexible Model and a Hybrid Exact Method for Integrated Employee Timetabling and Production Scheduling", Author manuscript, published in "Practice and Theory of Automated Timetabling VI, Brno Czech Republic (2006). 10.1007/978-3-540-77345-0_5 Koichi Nara, Tomomi Takeyama & Hyurchul kim, " A New Evolutionary Algorithm based on sheep flock heredity model & its application to scheduling problem , IEEE Transactions, Volume No. 1, Pg. No. 503-508 (1999). 10.1109/icsmc.1999.816603