全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

Reduction and Analysis of a Max-Plus Linear System to a Constraint Satisfaction Problem for Mixed Integer Programming

DOI: 10.4236/ajor.2017.72008, PP. 113-120

Keywords: Max-Plus Algebra, Scheduling, Critical Path, Constraint Satisfaction Problems, Mixed Integer Programing

Full-Text   Cite this paper   Add to My Lib

Abstract:

This research develops a solution method for project scheduling represented by a max-plus-linear (MPL) form. Max-plus-linear representation is an approach to model and analyze a class of discrete-event systems, in which the behavior of a target system is represented by linear equations in max-plus algebra. Several types of MPL equations can be reduced to a constraint satisfaction problem (CSP) for mixed integer programming. The resulting formulation is flexible and easy-to-use for project scheduling; for example, we can obtain the earliest output times, latest task-starting times, and latest input times using an MPL form. We also develop a key method for identifying critical tasks under the framework of CSP. The developed methods are validated through a numerical example.

References

[1]  Goto, H. (2017) Reduction of Max-Plus Algebraic Equations to Constraint Satisfaction Problems for Mixed Integer Programming. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science, E100-A, 427-430.
[2]  Heidergott, B., Olsder, G.J. and Woude, L. (2006) Max Plus at Work: Modeling and Analysis of Synchronized Systems. Princeton University Press, New Jersey.
[3]  Baccelli, F., Cohen, G., Older, G.J., and Quadrat, J.P. (1992) Synchronization and Linearity. An Algebra for Discrete Event Systems, John Wiley & Sons, New York.
[4]  Goto, H., and Masuda, S. (2004) On the Properties of the Greatest Subsolution for Linear Equations in the Max-Plus Algebra. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science, E87-A, 424-432.
[5]  Goto, H. (2013) Address a Project Scheduling Problem using Max-Plus Algebra. Journal of the Society of Instrument and Control Engineers, 52, 1083-1089.
[6]  Yokoyama, H. and Goto, H. (2016) Resolution of Resource Contentions in the CCPM-MPL Using Simulated Annealing and Genetic Algorithm. American Journal of Operations Research, 6, 480-488.
https://doi.org/10.4236/ajor.2016.66044

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133