OptaPlanner：Java规划引擎深度解析

OptaPlanner

负载均衡

需积分: 48 79 浏览量更新于2023-03-16 收藏 6.87MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

"OptaPlanner使用文档" OptaPlanner是一个强大的Java规划引擎，专为解决商业资源调度和规划问题而设计。它提供了一种智能的负载均衡解决方案，适用于各种业务场景，如云资源分配、旅行销售员问题、晚餐派对安排等。OptaPlanner是基于JBOSS开发的纯Java应用，旨在处理复杂的优化问题。 **1. Planner介绍** 1.1. 什么是OptaPlanner？ OptaPlanner是一个开源的、动态的优化框架，能够自动找到最优化解决方案，用于处理有限资源的分配问题。它能处理复杂的业务逻辑，通过迭代搜索来寻找最佳解。 1.2. 什么是规划问题？规划问题通常是指NP完全问题，意味着找到最佳解决方案的时间复杂度随问题规模呈指数增长。这些问题包含硬约束和软约束，前者必须被满足，而后者则是在保持可行解的同时尽可能优化的目标。 1.2.1. 规划问题的NP完全性 NP完全问题在计算复杂性理论中是极具挑战性的，因为它们的解法通常在问题规模增加时变得非常困难。 1.2.2. 规划问题的约束规划问题有硬约束和软约束之分，硬约束是必须满足的规则，而软约束是希望尽量优化的部分。 1.2.3. 规划问题的巨大搜索空间由于可能的解决方案数量巨大，搜索最优解需要高效的算法和技术。 1.3. 下载和运行示例用户可以从官方渠道下载OptaPlanner的发行版zip文件，然后在IDE（如IntelliJ, Eclipse, NetBeans）中运行示例项目。此外，还可以通过Maven, Gradle, Ivy, Buildr或ANT集成到现有项目中，或者直接从源代码构建OptaPlanner。 1.4. OptaPlanner的状态 OptaPlanner的版本6.1.0.Final代表了其成熟和稳定的状态，具备了丰富的功能和优化性能。 1.5. 兼容性 OptaPlanner与其他技术，如Drools和jBPM，具有良好的兼容性，可以协同工作，提供全面的业务规则管理和流程自动化解决方案。 1.6. 与Drools和jBPM的关系 OptaPlanner是Red Hat企业级产品的一部分，与Drools（一个规则引擎）和jBPM（一个业务流程管理平台）共同构成了强大的决策管理工具集。 1.7. 问题、问题和博客对于使用过程中遇到的问题，用户可以通过官方渠道提问、查找已知问题或阅读博客获取更多帮助。 **2. 快速入门** OptaPlanner提供了云平衡教程作为快速上手的示例，涵盖了问题陈述、问题规模、领域模型图、主方法、求解器配置、领域模型实现和分数配置等步骤，帮助开发者快速理解如何使用OptaPlanner。 **3. 应用案例和示例** 3.1. 示例概述 OptaPlanner提供了一系列示例，涵盖基础到高级的应用场景，包括但不限于： - 皇后问题（NQueens） - 云平衡（CloudBalancing） - 旅行销售员问题（TSP） - 晚餐派对安排（DinnerParty） - 网球俱乐部赛程安排（TennisClubScheduling）这些示例展示了OptaPlanner在不同领域的广泛应用，帮助开发者理解和实践规划问题的解决方案。通过深入学习OptaPlanner的文档和示例，开发者能够掌握如何利用该框架解决实际业务中的优化问题，实现高效的资源分配和负载均衡。无论是简单的还是复杂的规划问题，OptaPlanner都能提供强大的支持。

资源详情

资源推荐

Example 2.7. cloudBalancingScoreRules.drl - hard constraints

...

import org.optaplanner.examples.cloudbalancing.domain.CloudBalance;

import org.optaplanner.examples.cloudbalancing.domain.CloudComputer;

import org.optaplanner.examples.cloudbalancing.domain.CloudProcess;

global HardSoftScoreHolder scoreHolder;

// ############################################################################

// Hard constraints

// ############################################################################

rule "requiredCpuPowerTotal"

when

$computer : CloudComputer($cpuPower : cpuPower)

$requiredCpuPowerTotal : Number(intValue > $cpuPower) from accumulate(

CloudProcess(

computer == $computer,

$requiredCpuPower : requiredCpuPower),

sum($requiredCpuPower)

)

then

scoreHolder.addHardConstraintMatch(kcontext, $cpuPower - $requiredCpuPowerTotal.intValue());

end

rule "requiredMemoryTotal"

...

end

rule "requiredNetworkBandwidthTotal"

...

end

Next, if those constraints are met, we want to minimize the maintenance cost, so we add that as a soft constraint:

Example 2.8. cloudBalancingScoreRules.drl - soft constraints

// ############################################################################

// Soft constraints

// ############################################################################

rule "computerCost"

when

$computer : CloudComputer($cost : cost)

exists CloudProcess(computer == $computer)

then

scoreHolder.addSoftConstraintMatch(kcontext, - $cost);

end

If you use the Drools rule engine for score calculation, you can integrate with other Drools technologies, such as decision

tables (XLS or web based), the KIE Workbench rule repository, ...

2.1.8. Beyond this tutorial

Now that this simple example works, try going further. Enrich the domain model and add extra constraints such as these:

Each Process belongs to a Service. A computer can crash, so processes running the same service should be assigned to

different computers.

Each Computer is located in a Building. A building can burn down, so processes of the same services should be assigned

to computers in different buildings.

Chapter 3. Use cases and examples

3.1. Examples overview

3.2. Basic examples

3.2.1. N queens

3.2.2. Cloud balancing

3.2.3. Traveling salesman (TSP - Traveling salesman problem)

3.2.4. Dinner party

3.2.5. Tennis club scheduling

3.3. Real examples

3.3.1. Course timetabling (ITC 2007 track 3 - Curriculum course scheduling)

3.3.2. Machine reassignment (Google ROADEF 2012)

3.3.3. Vehicle routing

3.3.4. Project job scheduling

3.3.5. Hospital bed planning (PAS - Patient admission scheduling)

3.4. Difficult examples

3.4.1. Exam timetabling (ITC 2007 track 1 - Examination)

3.4.2. Employee rostering (INRC 2010 - Nurse rostering)

OptaPlanner User Guide

第16页共130页 2014年12月11日 16:39

3.4.3. Traveling tournament problem (TTP)

3.1. Examples overview

OptaPlanner has several examples. In this manual we explain OptaPlanner mainly using the n queens example and cloud

balancing example. So it's advisable to read at least those sections.

The source code of all these examples is available in the distribution zip under examples/sources and also in git under

optaplanner/optaplanner-examples.

Table 3.1. Examples overview

SpeExample Domain Size Competition? Special features used

N queens

1 entity class

1 variable

Entity <= 256

Value <= 256

Search space

<= 10^616

Pointless

(cheatable)

None

Cloud balancing

1 entity class

1 variable

Entity <= 2400

Value <= 800

Search space

<= 10^6967

Definied by us

Real-time planning

Traveling salesman

1 entity class

1 chained

variable

Entity <= 980

Value <= 980

Search space

<= 10^2927

Unrealistic

TSP web

Real-time planning

Dinner party

1 entity class

1 variable

Entity <= 144

Value <= 72

Search space

<= 10^310

Unrealistic

Decision Table

spreadsheet for score

constraints

Tennis club

scheduling

1 entity class

1 variable

Entity <= 72

Value <= 7

Search space

<= 10^60

Definied by us

Fairness score constraints

Immovable entities

Course timetabling

1 entity class

2 variables

Entity <= 434

Value <= 25 and

<= 20

Search space

<= 10^1171

Realistic

ITC 2007

track 3

Immovable entities

Machine

reassignment

1 entity class

1 variable

Entity <= 50000

Value <= 5000

Search space

<= 10^184948

Nearly

realistic

ROADEF

2012

Real-time planning

Vehicle routing

1 entity class

1 chained

variable

1 shadow entity

class

1 automatic

shadow variable

Entity <= 134

Value <= 141

Search space

<= 10^285

Unrealistic

VRP web

VariableListener

Real-time planning

Vehicle routing with

time windows

Extra on Vehicle

routing:

1 shadow

variable

Entity <= 1000

Value <= 1250

Search space

<= 10^3000

Unrealistic

VRP web

VariableListener

Real-time planning

Project job

scheduling

1 entity class

2 variables

1 shadow

variable

Entity <= 640

Value <= ? and

<= ?

Search space

<= ?

Nearly

realistic

MISTA 2013

Bendable score

VariableListener

Hospital bed

planning

1 entity class

1 nullable

variable

Entity <= 2750

Value <= 471

Search space

Unrealistic

Kaho PAS

Overconstrained planning

OptaPlanner User Guide

第17页共130页 2014年12月11日 16:39

This documentation heavily uses the 4 queens puzzle as the primary example.

A proposed solution could be:

Figure 3.1. A wrong solution for the 4 queens puzzle

The above solution is wrong because queens A1 and B0 can attack each other (so can queens B0 and D0). Removing queen

B0 would respect the "no 2 queens can attack each other" constraint, but would break the "place n queens" constraint.

Below is a correct solution:

Figure 3.2. A correct solution for the 4 queens puzzle

All the constraints have been met, so the solution is correct. Note that most n queens puzzles have multiple correct

solutions. We'll focus on finding a single correct solution for a given n, not on finding the number of possible correct solutions

for a given n.

3.2.1.2. Problem size

4queens has 4 queens with a search space of 256.

8queens has 8 queens with a search space of 10^7.

16queens has 16 queens with a search space of 10^19.

32queens has 32 queens with a search space of 10^48.

64queens has 64 queens with a search space of 10^115.

256queens has 256 queens with a search space of 10^616.

The implementation of the N queens example has not been optimized because it functions as a beginner example.

Nevertheless, it can easily handle 64 queens. With a few changes it has been shown to easily handle 5000 queens and

more.

3.2.1.3. Domain model

Use a good domain model: it will be easier to understand and solve your planning problem. This is the domain model for the

n queens example:

public class Column {

private int index;

// ... getters and setters

}

public class Row {

private int index;

// ... getters and setters

}

public class Queen {

private Column column;

private Row row;

public int getAscendingDiagonalIndex() {...}

public int getDescendingDiagonalIndex() {...}

// ... getters and setters

}

A Queen instance has a Column (for example: 0 is column A, 1 is column B, ...) and a Row (its row, for example: 0 is row 0, 1 is

row 1, ...). Based on the column and the row, the ascending diagonal line as well as the descending diagonal line can be

calculated. The column and row indexes start from the upper left corner of the chessboard.

public class NQueens implements Solution<SimpleScore> {

OptaPlanner User Guide

第19页共130页 2014年12月11日 16:39

private int n;

private List<Column> columnList;

private List<Row> rowList;

private List<Queen> queenList;

private SimpleScore score;

// ... getters and setters

}

A single NQueens instance contains a list of all Queen instances. It is the Solution implementation which will be supplied to,

solved by and retrieved from the Solver. Notice that in the 4 queens example, NQueens's getN() method will always return 4.

Table 3.2. A solution for 4 queens shown in the domain model

A solution Queen columnIndex rowIndex

ascendingDiagonalIndex

(columnIndex +

rowIndex)

descendingDiagonalIndex

(columnIndex - rowIndex)

A1 0 1 1 (**) -1

B0 1 0 (*) 1 (**) 1

C2 2 2 4 0

D0 3 0 (*) 3 3

When 2 queens share the same column, row or diagonal line, such as (*) and (**), they can attack each other.

3.2.2. Cloud balancing

This example is explained in a tutorial.

3.2.3. Traveling salesman (TSP - Traveling salesman problem)

3.2.3.1. Problem statement

Given a list of cities, find the shortest tour for a salesman that visits each city exactly once.

The problem is defined by Wikipedia. It is one of the most intensively studied problems in computational mathematics. Yet,

in the real world, it's often only part of a planning problem, along with other constraints, such as employee shift rostering

constraints.

3.2.3.2. Problem size

dj38 has 38 cities with a search space of 10^58.

europe40 has 40 cities with a search space of 10^62.

st70 has 70 cities with a search space of 10^126.

pcb442 has 442 cities with a search space of 10^1166.

lu980 has 980 cities with a search space of 10^2927.

3.2.4. Dinner party

3.2.4.1. Problem statement

Miss Manners is throwing another dinner party.

This time she invited 144 guests and prepared 12 round tables with 12 seats each.

Every guest should sit next to someone (left and right) of the opposite gender.

And that neighbour should have at least one hobby in common with the guest.

At every table, there should be 2 politicians, 2 doctors, 2 socialites, 2 coaches, 2 teachers and 2 programmers.

And the 2 politicians, 2 doctors, 2 coaches and 2 programmers shouldn't be the same kind at a table.

Drools Expert also has the normal Miss Manners example (which is much smaller) and employs an exhaustive heuristic to

solve it. OptaPlanner's implementation is far more scalable because it uses heuristics to find the best solution and Drools

Expert to calculate the score of each solution.

3.2.4.2. Problem size

wedding01 has 18 jobs, 144 guests, 288 hobby practicians, 12 tables and 144 seats with a search space of 10^310.

3.2.5. Tennis club scheduling

3.2.5.1. Problem statement

OptaPlanner User Guide

第20页共130页 2014年12月11日 16:39

剩余129页未读，继续阅读

丢灬丢

粉丝: 3
资源: 1

会员权益专享

OptaPlanner：Java规划引擎深度解析

OptaPlanner中文使用手册

OptaPlanner中文版

OptaPlanner中文手册

GUI程序如何调用optaplanner

OptaPlanner教程

optaplanner

optaplanner中文手册

optaplanner 生产排产

optaplanner demo

optaplanner 详解

optaplanner 输入几个地点路线规划

optaplanner安装教程

optaplanner c#

optaplanner 车间调度

多机调度问题java

@problemfactcollectionproperty

推荐开源 APS 高级排程系统

ALNS求解车间调度

Java有解决非线性规划问题的库吗

jdk17和jdk20

会员权益专享

最新资源