Development of the Contiguous-cells Transportation Problem

  • O. E. Charles-Owaba Department of Industrial and Production Engineering, University of Ibadan, Nigeria
  • V. Oladokun Department of Industrial and Production Engineering, University of Ibadan, Nigeria
  • O. Okunade Department of Industrial and Production Engineering, University of Ibadan, Nigeria
Keywords: Contiguous-cells Transportation Model, Production Maintenance Scheduling, Linear Optimization


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.


Download data is not yet available.


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

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

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

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

E. Bowman, “Production scheduling by the transportation method of linear programming”, Operations Research, Vol. 4, No. 1, pp. 100-103, 1956

G. Buttazzo, Hard real-time computing systems: predictable scheduling algorithms and applications, Spinger-Verlag, New York, 2005

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

J. Garcia, S. Lozano, “Production and delivery scheduling problem with time windows”, Computers & Industrial Engineering, Vol. 48, No. 4, pp. 733-742, 2005

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Abstract Views: 328
PDF Downloads: 75

Metrics Information
Bookmark and Share