A Flexible Job Shop Scheduling Problem with Controllable Processing Times to Optimize Total Cost of Delay and Processing

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, University of Kashan, Kashan, Iran

2 Department of Industrial Engineering, Faculty of Engineering, Tarbiat Modares University, Tehran, Iran

Abstract

In this paper, the flexible job shop scheduling problem with machine flexibility and controllable process times is studied. The main idea is that the processing times of operations may be controlled by consumptions of additional resources. The purpose of this paper to find the best trade-off between processing cost and delay cost in order to minimize the total costs. The proposed model, flexible job shop scheduling with controllable processing times (FJCPT), is formulated as an integer non-linear programming (INLP) model and then it is converted into an integer linear programming (ILP) model. Due to NP-hardness of FJCPT, conventional analytic optimization methods are not efficient. Hence, in order to solve the problem, a Scatter Search (SS), as an efficient metaheuristic method, is developed. To show the effectiveness of the proposed method, numerical experiments are conducted. The efficiency of the proposed algorithm is compared with that of a genetic algorithm (GA) available in the literature for solving FJSP problem. The results showed that the proposed SS provide better solutions than the existing GA.

Keywords

Main Subjects

References

Akturk, M.S. and T. Ilhan, (2011) Single CNC machine scheduling with controllable processing times to minimize total weighted tardiness. Computers & Operations Research, Vol. 38(4), pp. 771-781.
Bagheri, A. and M. Zandieh, (2011) Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—Variable neighborhood search approach". Journal of Manufacturing Systems, 2011. Vol. 30(1), pp. 8-15.
Barzegar, B. and H. Motameni, (2011) Optimality of the flexible job shop scheduling system based on Gravitational Search Algorithm". JOURNAL OF ADVANCES IN COMPUTER RESEARCH .
Blum, C. and A. Roli, (2003) Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys (CSUR), Vol. 35(3), pp. 268-308.
Brucker, P. and R. Schlie, (1990) Job-shop scheduling with multi-purpose machines". Computing, Vol. 45(4), pp. 369-375.
Chinneck, J.W., (2004) Practical optimization: a gentle introduction". Electronic document.
Dauzère-Pérès, S. and J. Paulli, (1997) An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search". Annals of Operations Research, Vol. 70, pp. 281-306.
Feng, M., et al., (2008) A Grouping Particle Swarm Optimization Algorithm for Flexible Job Shop Scheduling Problem, pp. 332-336.
Garey, M.R., D.S. Johnson, and R. Sethi, (1976) The complexity of flowshop and job-shop scheduling". Mathematics of Operations Research, Vol. 1, pp. 117-129.
Glover, F., M. Laguna, and R. Martí, (2000) Fundamentals of scatter search and path relinking". Control and cybernetics, Vol. 39(3), pp. 653-684.
Glover, F. (1998) A template for scatter search and path relinking. in Artificial evolution. Springer.
Giglio, D. (2015) Optimal control strategies for single-machine family scheduling with sequence-dependent batch setup and controllable processing times, Journal of Scheduling, Vol.18(5), pp. 525-543.
Haq, A.N., et al., (2007) A scatter search approach for general flowshop scheduling problem . The International Journal of Advanced Manufacturing Technology, Vol. 31(7-8), pp. 731-736.
Herroelen, W., B. De Reyck, and E. Demeulemeester, (1998) Resource-constrained project scheduling: a survey of recent developments. Computers & Operations Research, Vol. 25(4), pp. 279-302.
Janiak, A., (1989) Minimization of resource consumption under a given deadline in the two-processor flow-shop scheduling problem. Information Processing Letters, Vol. 32(3), pp. 101-112.
Jiang, S., Liu, M., Hao, J., Qian, W. (2015) A bi-layer optimization approach for a hybrid flow shop scheduling problem involving controllable processing times in the steelmaking industry, Computers and Industrial Engineering, Vol.87, pp. 518-531.
Karabati, S., P. Kouvelis, and G. Yu, (1995) The discrete resource allocation problem in flow lines. Management Science, Vol. 41(9), pp. 1417-1430.
Kayvanfar, V., I. Mahdavi, and G.M. Komaki, (2011) Single machine scheduling with controllable processing times to minimize total tardiness and earliness. Computers & Industrial Engineering.
Koca, E., Yaman, H., Aktürk, M.S. (2015) Stochastic lot sizing problem with controllable processing times, Omega, Vol. 53, pp. 1-10.
Luo, C. (2015) Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times, Numerical Algebra, Control and Optimization, Vol. 5(1), pp. 71-77.
Laguna, M., R. Martín, and R.C. Martí, (2003) Scatter search: methodology and implementations in C. Vol. 24.: Springer.
Li, J.-Q., et al., (2010) A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem". The International Journal of Advanced Manufacturing Technology, Vol. 52(5-8), pp. 683-697.
Mokhtari, H., I.N.K. Abadi and A. Cheraghalikhani, (2011a) A multi-objective flow shop scheduling with resource-dependent processing times: Tradeoff between makes pan and cost of resources. Int.J. Prod. Res., Vol. 49, pp. 5851-5875. 
Mokhtari, H., Nakhai Kamal Abadi, I., Zegordi, S.H., (2011b) Production Capacity Planning and Scheduling in a No-Wait Environment with Controllable Processing Times: An integrated modeling approach", Expert Systems with Applications, Vol. 38, pp. 12630-12642. 
Mokhtari, H. (2015) Designing an efficient bi-criteria iterated greedy heuristic for simultaneous order scheduling and resource allocation: a balance between cost and lateness measures", Neural Computing and Applications, Vol. 26, pp. 1085-1101.
Shioura, A., Shakhlevich, N.V., Strusevich, V.A. (2015) Optimal control strategies for single-machine family scheduling with sequence-dependent batch setup and controllable processing times, Mathematical Programming, Vol. 153(2), pp. 495-534.
Shirinivas, S.G., S. Vetrivel, and D. N.M.Elango, (2010) Applications of graph theory in computer science an overview". International Journal of Engineering Science and Technology, Vol. 2(9), pp. 4610-4621.
Tay, J.C. and N.B. Ho (2008) Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems". Computers & Industrial Engineering, Vol. 54(3), pp. 453-473.
Vokurka, R.J. and S.W.O. Leary-Kelly, (2000) A review of empirical research on manufacturing flexibility. Journal of Operations Management 2000.
Wang, L., et al . , (2011) An effective artificial bee colony algorithm for the flexible job-shop scheduling problem". The International Journal of Advanced Manufacturing Technology, Vol. 60(1-4), pp. 303-315.
Wang, J.-B., (2006) Single machine scheduling with common due date and controllable processing times". Applied Mathematics and Computation, Vol. 174(2), pp. 1245-1254.
Xia, W. and Z. Wu, (2005) An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, Vol. 48(2), pp. 409-425.
Yin, P.-Y., et al., (2010) Cyber swarm algorithms–improving particle swarm optimization using adaptive memory strategies. European Journal of Operational Research, Vol. 201, pp. 377-389.
Zhang, G., L. Gao, and Y. Shi, (2011) An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications, Vol. 38(4), pp. 3563-3573.
Zribi, N., et al., (2006) Minimizing the total tardiness in a flexible job-shop. World Automation Congress.
International Journal of Supply and Operations Management
Volume 2, Issue 3 - Serial Number 3
November 2015
Pages 871-887

Files

Share

How to cite

Statistics