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

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.

Resolution of Resource Contentions in the CCPM-MPL Using Simulated Annealing and Genetic Algorithm

This research aims to plan a “good-enough” schedule with leveling of resource contentions. We use the existing critical chain project management-max-plus linear framework. Critical chain project management is known as a technique used to both shorten the makespan and observe the due date under limited resources;the max-plus linear representation is an approach for modeling discrete event systems as production systems and project scheduling. If a contention arises within a single resource, we must resolve it by appending precedence relations. Thus, the resolution framework is reduced to a combinatorial optimization. If we aim to obtain the exact optimal solution, the maximum computation time is longer than 10 hours for 20 jobs. We thus experiment with Simulated Annealing (SA) and Genetic Algorithm (GA) to obtain an approximate solution within a practical time. Comparing the two methods, the former was beneficial in computation time, whereas the latter was better in terms of the performance of the solution. If the number of tasks is 50, the solution using SA is better than that using GA.

Image based measurements for evaluation of pelvic organ prolapse

Magnetic resonance imaging (MRI) measurements are essential for the diagnosis of pelvic organ prolapse given the inaccuracy of clinical examination. However, MRI pelvic floor measurements are currently performed manually and can be inconsistent and time-consuming. In this paper, we present a scheme for semi-automatic measurement modeling on MRI based on image segmentation and intersecting point identification methods. The segmentation algorithm is a multi-stage mechanism based on block grouping, support vector machine classification, morphological operation and prior shape information. Block grouping is achieved by classifying blocks as bone or background based on image texture features. The classified blocks are then used to find the initial segmentation by the first phase morphological opening. Prior shape information is incorporated into the initial segmentation to obtain the final segmentation using registration with the similarity type transformation. After segmentation, points of reference that are used for pelvic floor measurements are identified using morphological skeleton operation. The experiments on the MRI images show that the presented scheme can detect the points of reference on the pelvic floor structure to determine the reference lines needed for the assessment of pelvic organ prolapse. This will lead towards more consistent and faster pelvic organ prolapse diagnosis on dynamic MRI studies, and possible screening procedures for predicting predisposition to pelvic organ prolapse by radiologic evaluation of pelvic floor measurements.

QUADRATIC REPRESENTATION FOR ROADWAY PROFILE THAT MINIMIZES EARTHWORK COST

Roadway design usually involves choices regarding grade selection and earthwork (transportation) that can be solved using linear programming. Previous work considered the road profile as series of interconnected linear segments. In these models, constraints are included in the linear programming formulation to insure continuity of the road, which cause sharp connectivity points at the intersection of the linear segments. This sharp connectivity needs to be smoothed out after l;he linear programming solution is found and the earth in the smoothed portion of the roadway has to be moved to the landfill. In previous research, the smoothing issue is dealt with after an optimal solution is found. This increases the work required by the design engineer and consequently increases the construction cost; furthermore, the optimal solution is violated by this smoothing operation. In this paper, the issue of sharp connectivity points is resolved by representing the road profile by a quadratic function. The continuity constraints are dropped (unneeded) and global optimality is guaranteed. Moreover, no violation is incurred to implement the optimum results. Although a quadratic function is used to represent the road profile, the mathematical model is purely linear in nature.