Single machine scheduling - due dates constraints

Question

I am trying to program the single machine scheduling/bottleneck optimization, with python pulp, without making for loops to better understand.

I have 2 tasks called task1 and task2 to schedule that respectively last 1H and 3H, with due dates respectively at 1H and 4H.

Here are two solutions cases: first one is bad, the second one is good.

# Ko, because the task 1 due date is outdated  
# hours   1 2 3 4 
# task1         -
# task2   - - - 
              
# Ok, because due dates are respected
# hours   1 2 3 4 
# task1   - 
# task2     - - -

I want the pulp solver to find solution 2 above.

Here is my Pulp code, solution is close, maybe you can help me write the "due dates" type constraints, I can't do it.There are no FOR loops, it's done on purpose to try to understand...

import pulp as p

# Tasks
tasks = ["task1","task2"]
duration = {1,3}
due = {1,4}
starts = {1,2,3,4}

# Create problem
prob = p.LpProblem('single_machine_scheduling', p.LpMinimize)  

# Each possible "time slots" to select for tasks
task1_1 = p.LpVariable("task1_1", 0, None, p.LpBinary) 
task1_2 = p.LpVariable("task1_2", 0, None, p.LpBinary) 
task1_3 = p.LpVariable("task1_3", 0, None, p.LpBinary) 
task1_4 = p.LpVariable("task1_4", 0, None, p.LpBinary) 
task2_1 = p.LpVariable("task2_1", 0, None, p.LpBinary) 
task2_2 = p.LpVariable("task2_2", 0, None, p.LpBinary) 
task2_3 = p.LpVariable("task2_3", 0, None, p.LpBinary)  
task2_4 = p.LpVariable("task2_4", 0, None, p.LpBinary) 

# Theses constraints should be used for due dates constraints eventually...
start_1 = p.LpVariable("start_1", 0, None, p.LpContinuous) 
start_2 = p.LpVariable("start_2", 0, None, p.LpContinuous) 
start_3 = p.LpVariable("start_3", 0, None, p.LpContinuous) 
start_4 = p.LpVariable("start_4", 0, None, p.LpContinuous) 


# Objective : Minimize timespan
prob += 1 * task1_1 + 1 * task1_2 + 1 * task1_3 + 1 * task1_4 + 3 * task2_1 + 3 * task2_2 + 3 * task2_3 + 3 * task2_4

# Constraints

# Only one task1 and one task2 can be selected
prob +=  task1_1 + task1_2 + task1_3 + task1_4 == 1
prob +=  task2_1 + task2_2 + task2_3 + task2_4 == 1

# Due dates constraints ( How to ?)

# Solve
prob.solve()

# Print variables
for v in prob.variables():
    print(v.name, "=", v.varValue)
# Print objective
print("Minimized timespan = ", p.value(prob.objective))

start_3 = 0.0
start_4 = 0.0
task1_1 = 0.0
task1_2 = 0.0
task1_3 = 0.0
task1_4 = 1.0
task2_1 = 0.0
task2_2 = 0.0
task2_3 = 0.0
task2_4 = 1.0
Minimized timespan =  4.0

Maybe you can point me in the right direction? I also can't write them in the mathematical model, The ones I found include additional parameters like weight, but I don't want that here..

Edit: Oops sorry, I have learned that it's called "Total Tardiness minimization", and the Moore and Hodgson algorithm .

I'm not sure what you're trying to do here. You do not have 8 tasks. You have 2 tasks. The hours are not separate tasks. And you should be modelling the machine, not the tasks, right? When a task begins, does it need to be run to completion? The objective can't be to "minimize the timespan". The timespan required is fixed. It can't be minimized or maximized. You just need an arrangement that satisfies the constraints. — Tim Roberts, Jul 13 '23 at 21:54
This is not an optimization problem at all. It's a binary condition: "given all possible permutations of the tasks, which one(s) satisfy the constraints?" — Tim Roberts, Jul 13 '23 at 22:03
If you aren't voting (one way or the other) on answers to your [prior questions](https://stackoverflow.com/questions/76331274/pulp-conditional-constraint) or accepting them when you're satisfied, there is little incentive to answer new ones — Reinderien, Jul 14 '23 at 00:06
Hello Reinderien, My last question did not make sense, so I have erased it, sorry, the other one, I'm not sure how to vote. Thanks a lot Tim Roberts. — harmonius cool, Jul 14 '23 at 07:50

score 0 · Accepted Answer · answered Jul 13 '23 at 22:12

0

I just don't think this is a problem for pulp, because there's nothing to optimize. A simple pair of loops provides the most straightforward solution:

import itertools

tasks = [("task1", 1, 1), ("task2", 3, 4)]

# For each permutation
for tasklist in itertools.permutations(tasks):
    time = 1
    start = []
    order = []
    for task in tasklist:
        start.append( time )
        order.append( task )
        time += task[1]
        if time-1 > task[2]:
            # We violated a due date constraint.
            break
    else:
        print("Order",order,"succeeds")

Output:

Order [('task1', 1, 1), ('task2', 3, 4)] succeeds

answered Jul 13 '23 at 22:12

Tim Roberts

48,973
4
21
30

Thanks a lot, tim Roberts, I have understood. So I guess I might use Pulp to minimize the total tardiness instead ? – harmonius cool Jul 14 '23 at 07:53
Perhaps. As long as there **IS** a perfect solution, this code is better. Pulp might be able to come up with an arrangement that minimizes the tardiness when there is no "perfect" solution. – Tim Roberts Jul 14 '23 at 22:52

Single machine scheduling - due dates constraints

1 Answers1