私は線形最適化を初めて学んだので、古典的なスケジューリング問題に適用したいと思います。人材派遣の問題については、私は「シフト」の概念を捉える関数をどのように宣言するかについてはあまり明確ではない。私はこれまですごいとなっているojAlgoを使用していojAlgo線形最適化 - 作業シフトオーバーラップの防止?
。ここに私が考案した小さな問題があります。
SCENARIO:
You have three drivers to make deliveries.
Driver 1 costs $10/hr
Driver 2 costs $12/hr
Driver 3 costs $14/hr
Each driver can only work 3-6 hours a day.
Only one shift can be worked by a worker a day.
Operating day is 6:00 to 22:00, which must be fully covered.
Driver 2 cannot work after 11:00.
Create a schedule that minimizes the cost.
Solve Variables:
Tsx = shift start for Driver X
Tex = shift end for Driver X
Minimize:
10(Te1 - Ts1) + 12(Te2 - Ts2) + 14(Te3 - Ts3)
10Te1 - 10Te2 + 12Te2 - 12Ts2 + 14Te3 - 14Ts3
Constraints:
4.0 <= Te - Ts <= 6.0
6.0 <= Ts, Te <= 22.0
(Te1 - Ts1) + (Te2 - Ts2) + (Te3 - Ts3) = (22.0 - 6.0)
Te2 <= 11
ここに私がまとめたKotlinコードがあります。私は、それぞれのDriver
インスタンスができるだけ多くの関数入力を処理することがより容易であることを発見しました(これはOOPで興味深いパターンをもたらしました)。
import org.ojalgo.optimisation.ExpressionsBasedModel
import org.ojalgo.optimisation.Variable
fun main(args: Array<String>) {
val model = ExpressionsBasedModel()
val drivers = sequenceOf(
Driver(1, 10.0, model),
Driver(2, 12.0, model),
Driver(3, 14.0, model)
).map { it.driverNumber to it }
.toMap()
model.addExpression("EnsureCoverage")
.level(16.0)
.apply {
drivers.values.forEach {
set(it.shiftEnd, 1)
set(it.shiftStart, -1)
}
}
model.addExpression("Driver2OffAt11")
.upper(11)
.set(drivers[1]!!.shiftEnd, 1)
val result = model.minimise()
println(result)
}
data class Driver(val driverNumber: Int,
val rate: Double,
val model: ExpressionsBasedModel) {
val shiftStart = Variable.make("${driverNumber}shiftStart").weight(rate).lower(6).upper(22).apply(model::addVariable)
val shiftEnd = Variable.make("${driverNumber}shiftEnd").weight(rate).lower(6).upper(22).apply(model::addVariable)
init {
model.addExpression("${driverNumber}shiftLength")
.lower(4.0)
.upper(6.0)
.set(shiftEnd, 1)
.set(shiftStart, -1)
}
}
しかし、私は午前6時に割り当てられていたと同時に動作するようにすべての3つのドライバーを示すこの出力を取得しています。ドライバ1は6:00-11:00、ドライバ2は6:00-12:00、ドライバ3は6:00-11:00です。
OPTIMAL 624.0 @ [6.0, 11.0, 6.0, 12.0, 6.0, 11.0]
私は重複したくありません。私は一度に1人の運転手しか割り当てられないようにしたい、そして私は全営業日をカバーしたい。既に占有されている時間のバイナリ状態を表現するにはどうすればよいですか?
は、同様の問題の一例である[リンク](http://yetanothermathprogrammingconsultant.blogspot.com/2017/03/employee-scheduling-iv- direct.html)]。これには、代替の製剤およびアプローチへのリンクがあります。 –
それは、とにかくojAlgoに特有のモデリング問題です。スケジューリングや割り当てに関するGoogleの問題がある場合は、読むべきことがたくさんあることがわかります。 – apete