作业计划以最大程度地减少损失 [英] Job scheduling to minimise loss

问题描述

我遇到了工作安排问题.我们有开始时间，有时间 完成订单，截止日期.

I have got a job scheduling problem. We are given start time, time to complete the order, deadline.

假设start time + time complete <= deadline.

如果我无法做到的话，我也会蒙受的损失 在截止日期之前完成工作.我必须设计一种算法以最大程度地减少损失.

I have also been given the loss that will occur if I am not able to complete the job before the deadline. I have to design an algorithm to minimize the loss.

我尝试更改动态编程的标准算法，以最大程度地提高工作计划的利润，但没有成功.

I have tried changing the standard algorithm of dynamic programming for maximizing the profit in job scheduling but to no success.

我可以使用哪种算法来解决问题?

What algorithm can I use to solve the question?

推荐答案

由于违反了截止日期，因此问题看起来像是

Since the deadline can be violated, the problems looks like a Total Weighted Tardiness Scheduling Problem. There are many flavors of it, but most problems under this umbrella are computationally hard, therefore Dynamic Programming (DP) would not be my first choice. In my experience, DP also poses difficulties during modeling and implementation. Same comment for mathematical programming "as-is". Some approaches that can be implemented more quickly are:

1. 约束编程:学习曲线很小，并且其中包括许多库非常好的开源代码(大多数都有C ++ API).奖励:约束编程可以证明最优性.
2. 临时启发式:(1)以建设性算法(例如灵重和本地求解器 ，两者之间的一种混合方法:它使您可以使用类似于约束编程的形式主义对问题进行建模，然后使用启发式方法解决问题.它非常容易学习，通常可以让您快速入门，在我的测试中，它可以提供非常好的结果.

1. constraint programming: very small learning curve, and there are many libraries out there, included very good open source ones (most have C++ API). Bonus: constraint programming can demonstrate optimality.
2. ad hoc heuristics: (1) start with a constructive algorithm (like the greedy approach suggested by Ling Zhong and Flavio Giobergia), then (2) use some local search approach to improve if and finally (3) embed the approach into a metaheuristic scheme. This way you can build on top of the previous step, and learn a lot about the problem. Note: in general, heuristics cannot demonstrate optimality
3. special mention: local solver, a hybrid approach between the two above: it lets you model the problem using a formalism similar to constraint programming and then it solves it using heuristics. It is very easy to learn, it usually lets you get started quickly and, in my tests, it provides remarkably good results.

这篇关于作业计划以最大程度地减少损失的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！