Identical parallel machine scheduling with nonlinear deterioration and multiple rate modifying activities

Ömer Öztürkoğlu


This study focuses on identical parallel machine scheduling of jobs with deteriorating processing times and rate-modifying activities. We consider non linearly increasing processing times of jobs based on their position assignment. Rate modifying activities 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.


Parallel machine; scheduling; deterioration; rate-modifying activity

Full Text:



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).

Righter, R., Stochastic Scheduling . In: Skaked, M. and Shanthikumar, G. (Eds.), Academic Press, San Diego, CA, (1994).

Pinedo, M., Scheduling, Theory, Algorithms and Systems . Prentice-Hall, Englewood Clis, NJ, (1995).

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).

Gupta, J. and Gupta, S., Single Facility Scheduling with Nonlinear Processing Times . Computers and Industrial Engineering, 14:387{393, (1988).

Gupta, S., Kunnathur, A., and Dandapani, K., Optimal Repayment Policies for Multiple Loans . OMEGA, 15(4):323{330, (1987).

Tanaev, V., Gordon, V., and Shafransky, Y., Scheduling Theory, Single-stage Systems . Kluwer, Dordrecht, (1994).

Browne, S. and Yechiali, U., Scheduling Deteriorating Jobs on a Single Processor. Operations Research, 38:495{498, (1990).

Gawiejnowicz, S. and Pankowska, L., Scheduling Jobs with Varying Processing Times . Information Processing Letters, 54(3):175{178, (1995).

Kunnathur, A. and Gupta, S., Minimizing the Makespan with Late Start Penalties Added to Processing Times in a Single Facility Scheduling Prob-

lem . European Journal of Operational Research, 47(1):56{64, (1990).

Mosheiov, G., Scheduling Jobs With Step Deterioration ; Minimizing Makespan on a Single and Multi-Machine . Computers and Industrial Engineering, 28(4):869{879, (1995).

Ozturkoglu, Y. and Buln, R. L., A Unique Integer Mathematical Model for Scheduling Deteriorating Jobs with Rate-Modifying Activities on a Single Machine. The International Journal of Advanced Manufacturing Technology, 57(5 8):753{762, (2011).

Alidaee, B. and Womer, N., Scheduling with Time

Dependent Processing Times: Review and Exten-

sions. Journal of the Operational Research Society,

(7):711{721, (1999).

Cheng, T., Ding, Q., and Lin, B., A Concise Sur-

vey of Scheduling with Time-Dependent Processing

Times . European Journal of Operational Research,

:1{13, (2004).

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).

Chen, Z., Parallel Machine Scheduling with Time

Dependent Processing Times . Discrete Applied

Mathematics, 70:81{93, (1996).

Mosheiov, G., Multi-machine Scheduling with Linear

Deterioration. Infor, 36:205{214, (1998).

Kang, L. and Ng, C., A Note on a Fully Polynomial-

Time Approximation Scheme for Parallel-Machine

Scheduling with Deteriorating Jobs . International

Journal of Production Economics, 109:180{184,


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).

Ji, M. and Cheng, T., Parallel-Machine Scheduling of

Simple Linear Deteriorating Jobs . Theoretical Com-

puter Science, 410:3761{3768, (2009).

Lee, C.-Y. and Leon, V., Machine Scheduling with

Rate-Modifying Activity . European Journal of Op-

erational Research, 128:493{513, (2001).

Lee, C.-Y. and Lin, C.-S., Single Machine Scheduling

with Maintenance and Repair Rate-Modifying Ac-

tivities . European Journal of Operational Research,

:495{513, (2001).

Mosheiov, G. and Sidney, J., New Results on

Sequencing with Rate Modication . Information

Systems and Operational Research, 41(2):155{163,


Ozturkoglu, Y., A Bi-Criteria Single Machine Sched-

uling with Rate-Modifying-Activity. Gazi University

Journal of Science, 26(1):97{106, (2013).

Kim, B. S. and Ozturkoglu, Y., Scheduling a Sin-

gle Machine With Multiple Preventive Maintenance

Activities And Position-Based Deteriorations Using

Genetic Algorithms. The International Journal of

Advanced Manufacturing Technology, 67(5-8):1127{

, (2013).

Ozturkoglu, Y., An Ecient Time Algorithm for

Makespan Objectives. An International Journal of

Optimization and Control: Theories & Applications

(IJOCTA), 5(2), 75-80, (2015).

Lee, W.-C. and Wu, C.-C., Multi-Machine Schedul-

ing with Deteriorating Jobs and Scheduled Mainte-

nance . Applied Mathematical Modeling, 32:362{373,


Dalfard, V. M. and Mohammadi, G., Two Meta-

Heuristic Algorithms for Solving Multi-Objective

Flexible Job-Shop Scheduling with Parallel Machine

and Maintenance Constraints. Computers & Mathe-

matics with Applications, 64(6):2111{2117, (2012).

Cheng, B., Wang, Q., Yang, S., and Hu, X., An Im-

proved Ant Colony Optimization for Scheduling Iden-

tical Parallel Batching Machines With Arbitrary Job

Sizes. Applied Soft Computing, 13(2):765{772, (2013).

Wang, J.-B. and Wei, C.-M., Parallel Machine Sched-

uling With a Deteriorating Maintenance Activity

And Total Absolute Dierences Penalties. Applied

Mathematics and Computation, 217(20):8093{8099,


Wang, J.-J., Wang, J.-B., and Liu, F., Parallel Ma-

chines Scheduling With a Deteriorating Maintenance

Activity. Journal of the Operational Research Society,

(10):1898{1902, (2011).

Yang, D.-L. and Yang, S.-J., Unrelated Parallel-

Machine Scheduling Problems with Multiple Rate-

Modifying Activities. Information Sciences, 235:280{

, (2013).

Yang, D.-L., Cheng, T., and Yang, S.-J., Parallel-

Machine Scheduling With Controllable Processing

Times and Rate-Modifying Activities to Minimise To-

tal Cost Involving Total Completion Time and Job

Compressions. International Journal of Production

Research, 52(4):1133{1141, (2014).

Dorigo, M., Maniezzo, V., and Colorni, A., Posi-

tive Feedback as a Search Strategy . Technical Report

-016, Dip. Elettronica,Politecnico di Milano, Italy,


Sankar, S., Ponnambalam, S., Rathinavel, V., and

Visveshvaren, M., Scheduling in Parallel Machine

Shop: An Ant Colony Optimization Approach . In-

dustrial Technology, ICIT, IEEE Industrial Confer-

ence, pages 276{280, (2005).

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{

, (2002).

Alaykiran, K., Engin, O., and Doyen, A., Us-

ing Ant Colony Optimization to Solve Hybrid Flow-

shop Scheduling Problems . International Journal

of Advanced Manufacturing Technology, 35:541{550,


Arnaout, J.-P., Musa, R., and Rabadi, G., Ant

Colony Optimization Algorithm to Parallel Machine

Scheduling Problem with Setups . 4th IEEE Confer-

ence on Automation Science Engineering, Washing-

ton DC, USA, pages 578{582, (2008).

Arnaout, J.P. and Rabadi, G. and Musa, R. A Two-

Stage Ant Colony Optimization Algorithm to Mini-

mize the Makespan on Unrelated Parallel Machines

with Sequence-Dependent Setup Times . Journal of

Intelligent Manufacturing, 21(6), 693-701, (2010).

Rossi, A. and Boschi, E., A Hybrid Heuristic to

Solve the Parallel Machines Job-shop Scheuling Prob-

lem . Advance in Engineering Software, 40:118{127,


Behnamian, J., Zandieh, M., and Ghomi, S.,

Parallel-Machine Scheduling Problems with

Sequence-Dependent Setup Times using an ACO,

SA and VNS Hybrid Algorithm . Experts Systems

with Applications, 36:9637{9644, (2009).

Kirkpatrick, S., Gelatt, C., and Vecchi, M., Optimiza-

tion by Simulated Annealing . Science, 220:671{680,


Koulamas, C., Decomposition and Hybrid Simulated

Annealing Heuristics for the Parallel-Machine To-

tal Tardiness Problem . Naval Research Logistics,

:105{125, (1997).

Park, M.-W. and Kim, Y.-D., Search Heuristics for

a Parallel Machine Scheduling Problem with Ready

Times and Due Dates . Computers and Industrial En-

gineering, 33(3-4):793{796, (1997).

Jozefowska, J., Mika, M., Rozycki, R., and Waligora,

G., Local Search Metaheuristics for Discrete-

Continuous Scheduling Problems . European Journal

of Operational Research, 107:354{370, (1998).

Hindi, K. and Mhlanga, S., Scheduling Linearly De-

teriorating Jobs on Parallel Machines: A Simulated

Annealing Approach . Production Planning and Con-

trol, 12(1):76{80, (2001).

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{

, (2002).



  • There are currently no refbacks.

Copyright (c) 2017 ömer ozturkoglu

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.


   ithe_170     crossref_284         ind_131_43_x_117_117  Scopus  EBSCO_Host    ULAKBIM     ZBMATH more...