Search code examples
constraintsschedulingnonlinear-optimization

Formulating an optimization problem with non linear constraints

I am trying to solve a dynamic machine scheduling problem using what I think qualifies as a non linear programming constraints.

I have academic knowledge of linear programming techniques and appreciate the opportunity to try my hands at non linear programming.

However, before anything I am struggling to write down a well forumulated problem. Here is the situation:

  • I have a list of tasks of various natures that are ordered by "degree of emergency"
  • Several machines, that specialize in various tasks, work on those tasks based on the "degree of emergency" and their specialty
  • Tasks are not preemptive (start one, finish it, no interruption)
  • Completion time is statistically known based on the nature of the task and the machine assigned to it.
  • All machines should be used with minimal downtime
  • Workload is balanced: machines work on roughly the same number of tasks and work for the same amount of time total

Can you please help me properly formulate the problem? Here is how I started putting it:

  • m in M set of machines
  • S number of specialties
  • t in T set of tasks
  • time to complete task t by machine m
  • penalty coefficient for task t for being started with a delay past acceptable time
  • X_mt 1 if task t is assigned to machine m 0 otherwise

objective function: Find optimal X_mt such that task are started on time (limit penalty)

Objective function

constraints:

  • work duration is balanced through the machines (epsilon being a parameter):

balanced duration

  • number of work item is balanced through the machines (epsilon being a parameter):

balanced number

  • machine selects task for which it specializes (dotproduct m specialty/t characteristics )

specialization

  • minimize makespan

makespan

  • only assign 1 task per machine

singleton

I am also looking for an algorithm to find some epsilon-optimal solution based on how I relax the workload balancing parameter.

But before I can try to look for an algorithm, I need help to properly formulate the problem.

I've seen example where variance constraints are formulated as the minimization of the difference of upper and lower boundaries but I don't know how to apply it in this case since I have multiple variance constraints.

If this is too much, how would you translate this problem into a Reinforcement Learning one?

Solution

  • Let's look at one of the variance constraints:

    enter image description here

    is wrong IMHO. There should be no "for all m".

    I rewrite this as:

    v[m] = sum(t,d[m,t])  for all m 
variance(v) <= eps    (this is a single, scalar constraint)
   
<==>

v[m] = sum(t,d[m,t])  for all m
minv <= v[m]          for all m 
maxv >= v[m]          for all m
maxv - minv <= eps    (different eps. now to limit the bandwidth)
    • Similar for the other variance constraint
    • I don't see a good reason to add things to the objective.
    • This is completely linear