Identical parallel machine scheduling with nonlinear deterioration and multiple rate modifying activities
This study focuses on identical parallel machine scheduling of jobs with deteriorating processing times and rate-modifying activities. We consider nonlinearly increasing processing times of jobs based on their position assignment. Rate modifying activities (RMAs) are also considered to recover the increase in processing times of jobs due to deterioration. We also propose heuristics algorithms that rely on ant colony optimization and simulated annealing algorithms to solve the problem with multiple RMAs in a reasonable amount of time. Finally, we show that ant colony optimization algorithm generates close optimal solutions and superior results than simulated annealing algorithm.
[1] Mohring, R. and Rademacher, F., An Introduction to Stochastic Scheduling Problems . In: Neumann, K. and Pallaschke, D. (Eds.), Contributions to Operations Research, Springer, Berlin, (1985).
[2] Righter, R., Stochastic Scheduling . In: Skaked, M. and Shanthikumar, G. (Eds.), Academic Press, San Diego, CA, (1994).
[3] Pinedo, M., Scheduling, Theory, Algorithms and Systems . Prentice-Hall, Englewood Cliffs, NJ, (1995).
[4] Boudreau, J., Hopp, W., McClain, J., and Thomas, L., On the Interface Between Operations and Human Resources Management . Manufacturing and Service Operations Management, 5(3), 179–202, (2003).
[5] Gupta, J. and Gupta, S., Single Facility Scheduling with Nonlinear Processing Times . Computers and Industrial Engineering, 14, 387–393, (1988).
[6] Gupta, S., Kunnathur, A., and Dandapani, K., Optimal Repayment Policies for Multiple Loans . OMEGA, 15(4), 323–330, (1987).
[7] Tanaev, V., Gordon, V., and Shafransky, Y., Scheduling Theory, Single-stage Systems . Kluwer, Dordrecht, (1994).
[8] Browne, S. and Yechiali, U., Scheduling Deteriorating Jobs on a Single Processor . Operations Research, 38, 495–498, (1990).
[9] Gawiejnowicz, S. and Pankowska, L., Scheduling Jobs with Varying Processing Times . Information Processing Letters, 54(3), 175–178, (1995).
[10] Kunnathur, A. and Gupta, S., Minimizing the Makespan with Late Start Penalties Added to Processing Times in a Single Facility Scheduling Problem . European Journal of Operational Research, 47(1), 56– 64, (1990).
[11] Mosheiov, G., Scheduling Jobs With StepDeterioration ; Minimizing Makespan on a Single and Multi-Machine . Computers and Industrial Engineering, 28(4), 869–879, (1995)
[12] Ozturkoglu, Y. and Bulfin, R. L., A Unique Integer Mathematical Model for Scheduling DeterioratingJobs with Rate-Modifying Activities on a Single Machine. The International Journal of Advanced Manufacturing Technology, 57(5-8), 753–762, (2011).
[13] Alidaee, B. and Womer, N., Scheduling with Time Dependent Processing Times: Review and Extensions. Journal of the Operational Research Society, 50(7), 711–721, (1999).
[14] Cheng, T., Ding, Q., and Lin, B., A Concise Survey of Scheduling with Time-Dependent Processing Times . European Journal of Operational Research, 152, 1–13, (2004).
[15] Lodree, E., Geiger, C., and Jiang, X., Taxonomy for Integrating Scheduling Theory and Human Factors:Review and Research Opportunities . International Journal of Industrial Ergonomics, 39, 39–51, (2009).
[16] Chen, Z., Parallel Machine Scheduling with Time Dependent Processing Times . Discrete Applied Mathematics, 70, 81–93, (1996).
[17] Mosheiov, G., Multi-machine Scheduling with Linear Deterioration. Infor, 36, 205–214, (1998).
[18] Kang, L. and Ng, C., A Note on a Fully PolynomialTime Approximation Scheme for Parallel-Machine Scheduling with Deteriorating Jobs . International Journal of Production Economics, 109, 180–184, (2007).
[19] Ji, M. and Cheng, T., Parallel-Machine Scheduling with Simple Linear Deterioration to Minimize Total Completion Time . European Journal of Operational Research, 188, 341–347, (2008).
[20] Ji, M. and Cheng, T., Parallel-Machine Scheduling of Simple Linear Deteriorating Jobs . Theoretical Computer Science, 410, 3761–3768, (2009).
[21] Lee, C.-Y. and Leon, V., Machine Scheduling with Rate-Modifying Activity . European Journal of Operational Research, 128, 493–513, (2001).
[22] Lee, C.-Y. and Lin, C.-S., Single Machine Scheduling with Maintenance and Repair Rate-Modifying Activities . European Journal of Operational Research, 135, 495–513, (2001).
[23] Mosheiov, G. and Sidney, J., New Results on Sequencing with Rate Modification . Information Systems and Operational Research, 41(2), 155–163, (2003).
[24] Ozturkoglu, Y., A Bi-Criteria Single Machine Scheduling with Rate-Modifying-Activity. Gazi University Journal of Science, 26(1), 97–106, (2013).
[25] Kim, B. S. and Ozturkoglu, Y., Scheduling a Single Machine With Multiple Preventive Maintenance Activities And Position-Based Deteriorations Using Genetic Algorithms. The International Journal of Advanced Manufacturing Technology, 67(5-8), 1127– 1137, (2013).
[26] Ozturkoglu, Y., An Efficient Time Algorithm for Makespan Objectives. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 5(2), 75-80, (2015).
[27] Lee, W.-C. and Wu, C.-C., Multi-Machine Scheduling with Deteriorating Jobs and Scheduled Maintenance . Applied Mathematical Modeling, 32, 362–373, (2008)
[28] Dalfard, V. M. and Mohammadi, G., Two MetaHeuristic Algorithms for Solving Multi-Objective Flexible Job-Shop Scheduling with Parallel Machine and Maintenance Constraints. Computers & Mathematics with Applications, 64(6), 2111–2117, (2012).
[29] Cheng, B., Wang, Q., Yang, S., and Hu, X., An Improved Ant Colony Optimization for Scheduling Identical Parallel Batching Machines With Arbitrary Job Sizes. Applied Soft Computing, 13(2):765–772, (2013).
[30] Wang, J.-B. and Wei, C.-M., Parallel Machine Scheduling With a Deteriorating Maintenance Activity And Total Absolute Differences Penalties. Applied Mathematics and Computation, 217(20), 8093–8099, (2011).
[31] Wang, J.-J., Wang, J.-B., and Liu, F., Parallel Machines Scheduling With a Deteriorating Maintenance Activity. Journal of the Operational Research Society, 62(10), 1898–1902, (2011).
[32] Yang, D.-L. and Yang, S.-J., Unrelated ParallelMachine Scheduling Problems with Multiple RateModifying Activities. Information Sciences, 235, 280– 286, (2013).
[33] Yang, D.-L., Cheng, T., and Yang, S.-J., ParallelMachine Scheduling With Controllable Processing Times and Rate-Modifying Activities to Minimise Total Cost Involving Total Completion Time and Job Compressions. International Journal of Production Research, 52(4), 1133–1141, (2014).
[34] Dorigo, M., Maniezzo, V., and Colorni, A., Positive Feedback as a Search Strategy . Technical Report 91-016, Dip. Elettronica,Politecnico di Milano, Italy, (1991).
[35] Sankar, S., Ponnambalam, S., Rathinavel, V., and Visveshvaren, M., Scheduling in Parallel Machine Shop: An Ant Colony Optimization Approach . Industrial Technology, ICIT, IEEE Industrial Conference, pages 276–280, (2005).
[36] Tkindt, V., Monmarche, N. Tercinet, F., and Laugt, D., An Ant Colony Optimization Algorithm to Solve a 2-Machine Bicriteria Flowshop Scheduling Problem . European Journal of Operational Research, 142, 250– 257, (2002).
[37] Alaykiran, K., Engin, O., and Doyen, A., Using Ant Colony Optimization to Solve Hybrid Flowshop Scheduling Problems . International Journal of Advanced Manufacturing Technology, 35, 541–550, (2007).
[38] Arnaout, J.-P., Musa, R., and Rabadi, G., Ant Colony Optimization Algorithm to Parallel Machine Scheduling Problem with Setups . 4th IEEE Conference on Automation Science Engineering, Washington DC, USA, pages 578–582, (2008).
[39] Arnaout, J.P. and Rabadi, G. and Musa, R. A TwoStage Ant Colony Optimization Algorithm to Minimize the Makespan on Unrelated Parallel Machines with Sequence-Dependent Setup Times . Journal of Intelligent Manufacturing, 21(6), 693-701, (2010).
[40] Rossi, A. and Boschi, E., A Hybrid Heuristic to Solve the Parallel Machines Job-shop Scheuling Problem . Advances in Engineering Software, 40, 118–127, (2009).
[41] Behnamian, J., Zandieh, M., and Ghomi, S., Parallel-Machine Scheduling Problems with SequenceDependent Setup Times using an ACO, SA and VNS Hybrid Algorithm . Experts Systems with Applications, 36, 9637–9644, (2009).
[42] Kirkpatrick, S., Gelatt, C., and Vecchi, M., Optimization by Simulated Annealing . Science, 220, 671–680, (1983).
[43] Koulamas, C., Decomposition and Hybrid Simulated Annealing Heuristics for the Parallel-Machine Total Tardiness Problem . Naval Research Logistics, 44, 105–125, (1997).
[44] Park, M.-W. and Kim, Y.-D., Search Heuristics for a Parallel Machine Scheduling Problem with Ready Times and Due Dates . Computers and Industrial Engineering, 33(3-4), 793–796, (1997).
[45] J´ozefowska, J., Mika, M., R´o˙zycki, R., and Walig´ora, G., Local Search Metaheuristics for DiscreteContinuous Scheduling Problems . European Journal of Operational Research, 107, 354–370, (1998).
[46] Hindi, K. and Mhlanga, S., Scheduling Linearly Deteriorating Jobs on Parallel Machines: A Simulated Annealing Approach . Production Planning and Control, 12(1), 76–80, (2001).
[47] Kim, D.-W., Kim, K.-H., Jang, W., and Chen, F., Unrelated Parallel Machine Scheduling with Setup Times Using Simulated Annealing . Robotics and Computer Integrated Manufacturing, 18(3-4), 223–231, (2002)