Optimization of Project Schedules in the Critical-Chain Project-Management Max-Plus-Linear Framework

Hiroyuki Goto; Alan T. Murray

doi:10.15866/iremos.v11i4.13485

Optimization of Project Schedules in the Critical-Chain Project-Management Max-Plus-Linear Framework

Hiroyuki Goto^(1*), Alan T. Murray⁽²⁾

^(*) Corresponding author

Authors' affiliations

DOI: https://doi.org/10.15866/iremos.v11i4.13485

Abstract

Focusing on projects with uncertain task duration times, we aim to minimize the makespan of a project under the framework of the critical-chain project management approach. In existing frameworks, no attention has been paid to optimality under the “good enough” goal. However, in situations where there are only limited available resources, it is clear that the processing sequence of tasks greatly affects the makespan of the project. Hence, we structure an optimization problem to obtain an exact optimal solution. A discrete algebraic system called max-plus algebra plays is key to calculate the objective-function value. We adhere to seek an exact solution, for which a branch-and-bound technique is relied upon. Through numerical experiments, we find that the computation time highly depends on the structure of precedence constraints and assignment of resources. The developed solver is able to obtain an optimal solution within practical time standards if the number of tasks is not greater than 20.
Copyright © 2018 Praise Worthy Prize - All rights reserved.

Keywords

Critical-Chain Project Management; Max-Plus Algebra; Optimal Solution; Branch-And-Bound

Full Text:

PDF

References

E.M. Goldratt, Critical Chain (North River Press, 1997).

L.P. Leach, Critical Chain Project Management (Artech House, 2005).

R.C. Newbold, Project Management in the Fast Lane: Applying the Theory of Constraints (CRC Press, 1998).
http://dx.doi.org/10.1201/b18205

B. Heidergott, G.J. Olsder, and J. van der Woude, Max Plus at Work: Modeling and Analysis of Synchronized Systems (Princeton University Press, 2006).
http://dx.doi.org/10.1515/9781400865239

F. Baccelli, G. Cohen, G.J. Olsder, and J.P. Quadrat, Synchronization and Linearity: An Algebra for Discrete Event Systems (John Wiley & Sons, 1992).
http://dx.doi.org/10.2307/2583959

J. Komenda, S. Lahaye, J.L. Boimond, and T. van den Boom, Max-Plus Algebra and Discrete Event Systems, IFAC-PapersOnLine, Vol. 50, pp. 1784–1790. July 2017.
http://dx.doi.org/10.1016/j.ifacol.2017.08.163

M. Yurdakul, and N.G. Odrey, Development of a New Dioid Algebraic Model for Manufacturing with the Scheduling Decision Making Capability, Robotics and Autonomous Systems, Vol. 49, pp. 207–218. 2004.
http://dx.doi.org/10.1016/j.robot.2004.09.008

L. Hardouin, C.A. Maia, B. Cottenceau, and R.S. Mendes, Max-Plus Linear Observer: Application to Manufacturing Systems, IFAC Proceedings Volumes, Vol. 43, pp. 161–166. January 2010.
http://dx.doi.org/10.3182/20100830-3-de-4013.00028

A. Seleim, and H. ElMaraghy, Max-Plus Modeling of Manufacturing Flow Lines, Procedia CIRP, pp. 71–75. 2014.
http://dx.doi.org/10.1016/j.procir.2014.01.133

R. M. P. Goverde, Railway Timetable Stability Analysis Using Max-Plus System Theory, Transportation Research Part B: Methodological, Vol. 41, pp. 179–201. February 2007.
http://dx.doi.org/10.1016/j.trb.2006.02.003

L. Abdel-Malek, R. Montanari, and D. Meneghetti, The Capacitated Newsboy Problem with Random Yield: The Gardener Problem, International Journal of Production Economics, Vol. 115, pp. 113–127. September 2008.
http://dx.doi.org/10.1016/j.ijpe.2008.05.003

Y. I. Mahjoub, E. h. C. El-Alaoui, and A. Nait-Sidi-Moh, Modeling a Bus Network for Passengers Transportation Management Using Colored Petri Nets and (Max, +) Algebra, Procedia Computer Science, pp. 576–583. 2017.
http://dx.doi.org/10.1016/j.procs.2017.05.344

H. Goto, N. T. N. Truc, and H. Takahashi, Simple Representation of the Critical Chain Project Management Framework in a Max-Plus Linear Form, SICE J. Control Measure. Syst. Integrat., Vol. 6, pp. 341–344. June 2013.
http://dx.doi.org/10.9746/jcmsi.6.341

H. Goto, Forward-Compatible Framework with Critical-Chain Project Management Using a Max-Plus Linear Representation, OPSEARCH, Vol. 54, pp. 201–216. March 2017.
http://dx.doi.org/10.1007/s12597-016-0276-3

S. Yoshida, H. Takahashi, and H. Goto, Resolution of Time and Worker Conflicts for a Single Project in a Max-Plus Linear Representation, Ind. Eng. Manage. Syst., Vol. 10, pp. 279–287. December 2011.
http://dx.doi.org/10.7232/iems.2011.10.4.279

W. L. Peng, and H. Xu, The Scheduling Problem of Active Critical Chain Method, Information Technology Journal, Vol. 11, pp. 829–839. July 2012.
http://dx.doi.org/10.3923/itj.2012.829.839

H. Goto, and Y. Shimakawa, Extension of the Critical Chain Project Management Based Framework to Mimo-Structured Projects Using a Max-Plus-Linear Representation, The 10th triennial conference of the association of Asia-Pacific operational research societies. 2015.

F. S. Hillier, and G. J. Lieberman, Introduction to Operations Research (McGraw-Hill Higher Education, 2010).
http://dx.doi.org/10.2307/1267061

M. Pinedo, Scheduling: Theory, Algorithms, and Systems (Springer, 2012).
http://dx.doi.org/10.1007/978-3-642-46773-8_5

P. Brucker, Scheduling Algorithms (Springer, 2007).

T. H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms (MIT Press, 2009).

Refbacks

There are currently no refbacks.

Username
Password
Remember me