Optimizing Work Scheduling In Shop Floor Using Ant-Colony Algorithm

F. GILBERT JERALD, K. M. SENTHIL KUMAR

Abstract


A job shop manufacturing system is specifically designed to simultaneously produce different types of products in a shop floor. Job shop scheduling problems (JSSPs) have been studied extensively and most instances of JSSP are NP-hard, which implies that there is no polynomial time algorithm to solve them. As a result, many approximation methods have been explored to find near-optimal solutions within reasonable computational efforts. Furthermore, in a real world, JSSP is generally dynamic with continuous incoming jobs and providing schedules dynamically within constrained computational times in order to optimize the system performance becomes a great challenge. In this paper, Ant Colony Optimization Algorithm (ACO) is proposed to reduce the total completion time of shop floor projects. In this scheduling, the time is considered as a main factor. The works are scheduled as based on this time factor. Less time consumption of works is scheduled as first order and others are outsourced in this system. The experimental result shows that ACO the average percentage of reduction in makes span is up to 21.12%.
Keyword: task scheduling, ant colony optimization, completion time, shop floor projects.

Full Text:

PDF

References


Bean, J. (1994). Genetics and random keys for sequencing and optimization. ORSA Jornal of Computing 6, 154–160.

Wellman, M.P., W.E. Walsh, P. Wurman and J.K. MacKie-Mason (2001). Auction protocols for decentralized scheduling. Games and Economic Behavior 35, 271–303

McKay, K., M. Pinedo and S. Webster (2001). A practice-focused agenda for production scheduling research. Production and Operations Management.

Dorigo, Marco, Vittorio Maniezzo and Alberto Colorni (1996). Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B 26(1), 29–41.

Colorni, A., M. Dorigo, V. Maniezzo and M. Trubian (1994). Ant system for job-shop scheduling. JORBEL-Belgiuan Journal of Operations Research, Statistics and Computer Science 34(1), 39–53.

Cicirello, Vicent A. and Stephen F. Smith (2001). Ant colony for autonomous decentralized shop floor routing. In: Proceedings of ISADS-2001, Fifth International symposium on autonomous decentralized systems.

Pinedo, Michael (2002). Scheduling: Theory, Algorithms, and Systems. second ed.. Prentice Hall.

Hopp, W. J. and Spearman, M. L., 2000. Factory physics: Foundations of manufacturing management, 2nd Edition, Irwin McGraw-Hill.

Chryssolouris, G., 2006. Manufacturing systems, Theory and Practice, Springer- Verlag, New York.

RONG, Z., 2008. Dynamic Job Shop Scheduling Using Ant Colony Optimization Algorithm Based On A Multi-Agent System (Doctoral dissertation).

Pinedo, M., 2002. Scheduling theory, algorithms and systems. Second edition, Prentice Hall, Upper Saddle River, New Jersey.

Vollmann, T.E., Berry, W.L. and Whybark, D.C., 1992. Manufacturing Planning and Control Systems, Irwin, Homewood, IL.

Ovacik, I.M., and Uzsoy, R., 1994. Exploiting shop floor status information to schedule complex job shop. Journal of Manufacturing Systems, 13 (2), pp. 73-84.

Ovacik, I.M., and Uzsoy, R., 1997. Decomposition methods for complex factory scheduling problem, Kluwer, Dordrecht.

Dorigo, Marco, Vittorio Maniezzo and Alberto Colorni (1996). Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B 26(1), 29–41.

Gambardella, Luca Maria and Marco Dorigo (1996). Solving symmetric and asymmetric tsps by ant colonies. In: IEEE Conference on Evolutionary Computation (ICEC’96).

Silva, C.A., Thomas Runkler, J.M. Sousa and Rainer Palm (2002). Optimization of logistic processes using ant colonies. In: Proceedings of Agent- Based Simulation 3.




DOI: https://doi.org/10.37628/jcam.v1i1.109

Refbacks

  • There are currently no refbacks.