CFP last date
20 June 2024
Reseach Article

Heuristics Supported Local Search for Optimization of Multi Job Shop Scheduling

Published on None 2011 by M. Nandhini, S.Kanmani, Rajesh Kumar Sahoo
Artificial Intelligence Techniques - Novel Approaches & Practical Applications
Foundation of Computer Science USA
AIT - Number 2
None 2011
Authors: M. Nandhini, S.Kanmani, Rajesh Kumar Sahoo
249ebdba-5ee2-4695-9607-0bb57a889bab

M. Nandhini, S.Kanmani, Rajesh Kumar Sahoo . Heuristics Supported Local Search for Optimization of Multi Job Shop Scheduling. Artificial Intelligence Techniques - Novel Approaches & Practical Applications. AIT, 2 (None 2011), 1-6.

@article{
author = { M. Nandhini, S.Kanmani, Rajesh Kumar Sahoo },
title = { Heuristics Supported Local Search for Optimization of Multi Job Shop Scheduling },
journal = { Artificial Intelligence Techniques - Novel Approaches & Practical Applications },
issue_date = { None 2011 },
volume = { AIT },
number = { 2 },
month = { None },
year = { 2011 },
issn = 0975-8887,
pages = { 1-6 },
numpages = 6,
url = { /specialissues/ait/number2/2828-209/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Special Issue Article
%1 Artificial Intelligence Techniques - Novel Approaches & Practical Applications
%A M. Nandhini
%A S.Kanmani
%A Rajesh Kumar Sahoo
%T Heuristics Supported Local Search for Optimization of Multi Job Shop Scheduling
%J Artificial Intelligence Techniques - Novel Approaches & Practical Applications
%@ 0975-8887
%V AIT
%N 2
%P 1-6
%D 2011
%I International Journal of Computer Applications
Abstract

The main objective of the Multi Job Shop Scheduling problem (MJSSP) is to find a schedule of operations that can minimize the final completion time. In this paper, the various approaches with heuristics used to solve MJSSP are studied and its constraints clearly represented in mathematical model. MJSSP has been implemented with Steepest-Ascent Hill Climbing(SAHC) algorithm with constructive heuristics and compared against with the results of depth-first- Dynamic Consistency Enforcement(DCE) . Also SAHC’s efficiency is experimentally proved with more optimal and consistent results obtained for various instances.

References
  1. Mesghouni, K., Hammadi, S., and Borne, P. 2004. Evolutionary algorithms for Job-Shop Scheduling. Int. J. Applied Mathematics and Computer Science,14(10),(2004), 91-103.
  2. Pinedo,, M. 1995. Scheduling: theory, algorithms and systems . Englewood Cliffs, NJ; Prentice Hall.
  3. Holland, J.H 1992. Adaptation in Natural and Artificial Systems . MIT Press, Cambridge.
  4. Tamilarasi,A., Anantha Kumar, T. 2010. ”An enhanced genetic algorithm with simulated annealing for job-shop Scheduling. Int. J. of Engineering, Science and Technology, 2 (1), 144-151.
  5. Huiyuan, R., Lili, J., Xiaoying, X., and Muzhi, L. 2009. Heuristic optimization for dual-resource constrained job shop scheduling. In Proceedings of Int. Asia Conference on Informatics in Control, Automation and Robotics.
  6. Ping-Teng Chang, Yu-Ting Lo. 2001. Modeling of Job-shop Scheduling with Multiple Quantitative and Qualitative Objectives and a GA/TS Mixture approach. Int. J. Computer Integrated Manufacturing, 14(4),367-384..
  7. Hong Zhou, Waiman Cheung, Lawrence C. Leung. 2009. Minimizing Weighted Tardiness of Job-shop Scheduling Using a Hybrid Genetic Algorithm. European Journal of Operational Research, 194(3), 637-649.
  8. Li-Ning Xing, Ying-Wu Chen, Ke-Wei Yang. 2009. An Efficient Search Method for multi-objective Flexible Job Shop Scheduling Problems. Journal of Intelligent Manufacturing, 20(3),283-293.
  9. Adibi, M.A., Zandieh,M., and Amiri,M. 2010 . Multi-objective Scheduling of Dynamic Job Shop Using Variable Neighborhood Search. Expert Systems with Applications, 37(1), 282-287.
  10. Mahdavinejad, R.A .(2007). Multiple Job Shop-Scheduling using Hybrid Heuristic Algorithm. Int. J. Engineering and Natural Sciences,1 (1), 53-58.
  11. Nandhini,M., and Kanmani,S.2010. Design of Mathematical representation and optimization of course timetabling using local search. Int. J. of Combinatorial Optimization and Informatics,1(2), 20-30.
  12. Garrido, A., Salido, M.A., Barber, López, F.A. 2000. Heuristic Methods for Solving Job-Shop Scheduling Problems. ECAI-2000-Workshop on New Results in Planning, Scheduling and Design, 44-49.
  13. Sadeh, N.M., Sycara, K., and Xiong, Y. 1995. Backtracking techniques for the job-shop scheduling constraint satisfaction problem. Artificial Intelligence, 76,.455-480.
  14. Sadeh, N.M., and Fox, M.S. 1996. Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem. Artificial Intelligence, 86, 1-4.
  15. Garey, J.E., Johnson, D.S., and Sethi, R. 1976. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117–129.
  16. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B. 1993. Sequencing and scheduling: Algorithms and complexity. Handbooks in Operations Research and Management Science, 4, 445-552.
Index Terms

Computer Science
Information Sciences

Keywords

Constraints heuristics multi job shop scheduling mathematical model steepest ascent hill climbing depth first multi job shop scheduling mathematical model steepest ascent hill climbing depth first