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

• 作者: Hajime Yokoyama Hiroyuki Goto
• 来源期刊: 美国运筹学期刊(英文)
• 学科: 数学
• 关键词: Max-Plus ALGEBRA SCHEDULING Critical PATH CONSTRAINT SATISFACTION Problems Mixed INTEGER Programing
• 年，卷（期）: 2017,（2）
• 页码范围: 113-120
• 页数: 8页
• 分类号: O1

摘要

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.