Development of the Contiguous-cells Transportation Problem
Abstract
The issue of scheduling a long string of multi-period activities which have to be completed without interruption has always been an industrial challenge. The existing production/maintenance scheduling algorithms can only handle situations where activities can be split into two or more sets of activities carried out in non-contiguous sets of work periods. This study proposes a contiguous-periods production/maintenance scheduling approach using the Transportation Model. Relevant variables and parameters of contiguous-cells scheduling problem were taken from the literature. A scheduling optimization problem was defined and solved using a contiguous-cells transportation algorithm (CCTA) which was applied in order to determine the optimal maintenance schedule of a fleet of ships at a dockyard in South-Western Nigeria. Fifteen different problems were solved. It is concluded that the contiguous-cells transportation approach to production/ maintenance scheduling is feasible. The model will be a useful decision support tool for scheduling maintenance operations.
Keywords:
Contiguous-cells Transportation Model, Production Maintenance Scheduling, Linear OptimizationDownloads
References
T. Alam, R. Rastogi, “Transportation problem: extensions and methods – an overview”, VSRD International Journal of Business & Management Research, Vol. 1, No. 2, pp. 121-126, 2011
M. Pinedo, Planning and scheduling in manufacturing and services, Springer Science & Business Media. LLC, New York, 2005
V. Adlakha, K. Kowalski, B. Lev, “A branching method for the fixed charged transportation problem”, OMEGA, Vol. 38, No. 5, pp. 393-397, 2010 DOI: https://doi.org/10.1016/j.omega.2009.10.005
S. Aramuthakannan, P. Kandasamy, “Revised distribution method of finding optimal solution for transportation problems”, IOSR Journal of Mathematics, Vol. 4, No. 5, pp. 39-42, 2013 DOI: https://doi.org/10.9790/5728-0453942
K. Basy, B. B. Pal, A. Kundu, “An algorithm for the optimum time-cost trade-off in generalized solid transportational problem”, Optimization: A Journal of Mathematical Programming and Operations Research,Vol. 28, No. 2, pp. 171-185, 1993 DOI: https://doi.org/10.1080/02331939308843912
M. Basu, D. Acharya, “On quadratic fractional generalized solid bi-criterion transportation problem” Journal of Applied Mathematics and Computing, Vol. 10, No. 1-2, pp. 131-143, 2002 DOI: https://doi.org/10.1007/BF02936212
E. Bowman, “Production scheduling by the transportation method of linear programming”, Operations Research, Vol. 4, No. 1, pp. 100-103, 1956 DOI: https://doi.org/10.1287/opre.4.1.100
G. Buttazzo, Hard real-time computing systems: predictable scheduling algorithms and applications, Spinger-Verlag, New York, 2005 DOI: https://doi.org/10.1007/0-387-27578-9
O. Charles-Owaba, “Gantt charting multiple machines’ preventive maintenance activities”, Nigerian Journal of Engineering Research and Development, Vol. 1, No1 , pp. 60-67, 2002
G. Frederickson, “Scheduling unit-time tasks with integer release times and deadlines”, Information Processing Letters, Vol. 16, No. 4, pp. 171-173, 1983 DOI: https://doi.org/10.1016/0020-0190(83)90117-5
J. Garcia, S. Lozano, “Production and delivery scheduling problem with time windows”, Computers & Industrial Engineering, Vol. 48, No. 4, pp. 733-742, 2005 DOI: https://doi.org/10.1016/j.cie.2004.12.004
M. Garey, D. Johnson, B. Simons, R. Tarjan, “Scheduling unit-time tasks with arbitrary release times and deadlines”, SIAM J. Computing, Vol. 10, No. 2, pp. 256- 269, 1981 DOI: https://doi.org/10.1137/0210018
M. Göthe-Lundgren, J. Lundgren, J. Persson, “An optimization model for refinery production scheduling”, International Journal of Production Economics, Vol. 78 No. 3, pp. 255-270, 2002 DOI: https://doi.org/10.1016/S0925-5273(00)00162-6
L. George, P. Muhlethaler, N. Rivierre. “Optimality and non-preemptive real-time scheduling revisited” [Research Report] RR-2516, 1995,
K. Gupta, S. Arora, “Bottleneck capacitated transportation problem with bounds on rim conditions” OPSEARCH, Vol. 50, No. 4, pp. 491-503, 2013 DOI: https://doi.org/10.1007/s12597-013-0125-6
S. Huang, “A genetic-evolved fuzzy system for maintenance scheduling of generating units”, International Journal of Electrical Power & Energy Systems, Vol. 20, No. 3, pp. 191-195, 1998 DOI: https://doi.org/10.1016/S0142-0615(97)00080-X
V. Jayabalam, D. Chaudhuri, “Cost optimization of maintenance scheduling for a system with assured reliability”, IEEE Transactions on Reliability,Vol. 41, No.1, pp. 21-25, 1992 DOI: https://doi.org/10.1109/24.126665
K. Jeffay, D. Stanat, C. Martel, “On non-preemptive scheduling of periodic and sporadic tasks”, Proc. of the IEEE Real-Time Systems Symposium, San Antonio, Texas, USA, pp. 129–139, 1991
J. Józefowska, A. Zimniak, “Optimization tool for short-term production planning and scheduling”, International Journal of Production Economics, Vol. 112, No. 1, pp. 109–120, 2008 DOI: https://doi.org/10.1016/j.ijpe.2006.08.026
F. Khan, M. Haddara, “Risk based machine (RRM): A quantitative approach for maintenance/inspection scheduling and planning”, Journal of Loss Prevention in the Process Industries, Vol. 16, No. 6, pp. 561-573, 2003 DOI: https://doi.org/10.1016/j.jlp.2003.08.011
P. Kumarawadu, M. Nakamura, A. Yoshida, H. Hatazaki, “A method for appropriate maintenance scheduling of redundant pump systems in existing thermal power stations based on system availability”, International Journal of Systems Science, Vol. 30, No. 2, pp.157-163, 1999 DOI: https://doi.org/10.1080/002077299292506
K. Lee, B. Choi, “Two-stage production scheduling with an outsourcing option”, European Journal of Operational Research, Vol. 213, No. 3, pp. 489–497, 2011 DOI: https://doi.org/10.1016/j.ejor.2011.03.037
B. Lev, “A non iterative algorithm for tridiagonal transportation problems and its generalization”, Journal of Operations Research Society of America, Vol. 20, pp. 109-125, 1972 DOI: https://doi.org/10.1287/opre.20.1.109
M. Lohgaonkar, “Optimization fuzzy multi-objective multi-index transportation problem with linear membership function”, International Journal of Statistika and Mathematika, Vol. 4, No. 2, pp. 50-53, 2012
M. Lohgaonkar, V. Bajaj, V. Jadhav, “Additive fuzzy multiple goal programming model for unbalanced multi-objective transportation problem”, International Journal of Machine Intelligence, Vol. 2, No. 1, pp. 29-34, 2010 DOI: https://doi.org/10.9735/0975-2927.2.1.29-34
R. Malhotra, M. Puri, “Pricing of bottlenecks at optimal time in a transportation problem” in Combinatorial Optimization: Some aspects. R. Malhotra et al. Eds. Narosa Publishing House, New Delhi: India, 2007
D. Mohanta, P. Sadhu, R. Chakrabarti, “Fuzzy reliability evaluation of captive power plant maintenance scheduling incorporating uncertain forced outage rate and load representation”, Electric Power System Research, Vol. 72, No. 1, pp. 73-84, 2004 DOI: https://doi.org/10.1016/j.epsr.2004.04.001
P. Pandian, G. Natarajan, “A new method for solving bottleneck-cost transportation problems”, International Mathematical Forum, Vol 6, No. 10, pp. 451-460, 2011
Y. Sheng, K. Yao, “Fixed charge transportation problem and its uncertain programming model”, Industrial Engineering & Management Systems, Vol. 11, No. 2, pp. 183-187, 2012 DOI: https://doi.org/10.7232/iems.2012.11.2.183
M. Short, M. Pont, J. Fang, “Exploring the impact of pre-emption on dependability in time-triggered embedded systems: A pilot study”, 20th Euromicro conference on real-time systems (ECRTS 2008), Prague, Czech Republic, pp. 83-91, 2008 DOI: https://doi.org/10.1109/ECRTS.2008.14
H. Tamaki, M. Ochi, M. Araki, “Application of Genetics-Based Machine Learning to Production Scheduling”, 1996 Japan-USA Symposium on Flexible Automation, pp. 1221-1224, 1996
Downloads
How to Cite
License
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
