Identical parallel machine scheduling with nonlinear deterioration and multiple rate modifying activities
DOI:
https://doi.org/10.11121/ijocta.01.2017.00328Keywords:
Parallel machine, scheduling, deterioration, rate-modifying activityAbstract
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.
Downloads
References
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,
(2007).
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,
(2003).
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,
(2008).
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,
(2011).
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,
(1991).
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,
(2007).
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,
(2009).
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,
(1983).
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).
Downloads
Published
How to Cite
Issue
Section
License
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
