Job Scheduling Algorithm

Question

Changed Program based on suggestions. New Code: Job Scheduling Algorithm 2

I have created an algorithm for job scheduling.
The algorithm goes through sub-lists in order with two nested for loops. Inside the nested for loops, the algorithm counts how many tasks for each job are completed. If this is equal to the number of tasks, then the profit for that job is added to the total profit.

Item start to Item end is an item using that machine from start to end. Machine start to Machine end is when the machines can process the items. A single task is a single machine doing items. The number required for a job is tasks to be completed while done tasks are tasks that will finish in the schedule. If those two counts are equal then the job is done, and profit is added to the profit var.

Here is the code

def output_profit(profit:int)->None:
 print("profit: " + str(profit), end = "\n")
 
def output_subset(subset:[str])->None:
 for item in subset:
 print(str(item), end = " ")
def main():
 items = ["a", "b"]
 items_starts = [0, 3]
 items_ends = [2, 4]
 
 #total number of tasks that are needed for job i
 tasks_to_complete = [1,1] 
 
 #tasks that are done for job i 
 done_tasks = [0, 0]
 
 machine_starts = [0, 0]
 machine_ends = [1, 7]
 
 profits_for_job = [10, 12]
 profit = 0
 
 for row in range(0, len(items)):
 for col in range(0, len(items) + 1):
 subset = items[row:col]
 for job_index in range(0, len(subset)):
 if items_starts[job_index] >= machine_starts[job_index]:
 if items_ends[job_index] <= machine_ends[job_index]:
 done_tasks[job_index] = done_tasks[job_index] + 1
 profit = 0 
 for job_index in range(0, len(subset)):
 if tasks_to_complete[job_index] == done_tasks[job_index]:
 profit = profit + profits_for_job[job_index]
 
 output_profit(profit)
 output_subset(subset)
 
if __name__ == "__main__":
 main()

I am looking for ways to improve the code readability and improve the algorithm's efficiency.

• user228914: What do item_starts and item_ends do? I'd also appreciate if you thoroughly explained the purpose of all variables in main(), since a first glance it's very difficult to identify their purpose :)

Answer 1

Functions

It's good that you're thinking about how to capture code in functions, but you haven't particularly chosen the right code to move into functions.

This is somewhat trivial:

print("profit: " + str(profit), end = "\n")

and does not deserve its own function; simply write

print(f'profit: {profit}')

at the outer level. The same applies for output_subset, which does not need a loop and can be

 print(' '.join(item for item in subset))

Instead, something that does deserve to be in a separate function is your set of loops starting at for row, which can be translated into a generator; also note that 0 is the default start for range:

ProfitPair = Tuple[
 int,
 List[str],
]
def get_profits( ... variables needed for iteration ...) -> Iterable[ProfitPair]:
 for row in range(len(items)):
 for col in range(len(items) + 1):
 subset = items[row:col]
 for job_index in range(len(subset)):
 if items_starts[job_index] >= machine_starts[job_index]:
 if items_ends[job_index] <= machine_ends[job_index]:
 done_tasks[job_index] = done_tasks[job_index] + 1
 profit = 0 
 for job_index in range(len(subset)):
 if tasks_to_complete[job_index] == done_tasks[job_index]:
 profit += profits_for_job[job_index]
 
 yield (profit, subset)

Type hints

It's good that you've tried this out. subset:[str] should be subset: List[str].

Indexing

for row in range(0, len(items)):
 for col in range(0, len(items) + 1):
 subset = items[row:col]

seems strange to me. Based on your initialization, items is not a two-dimensional (nested) list - unless you count string indexing as the second dimension. row and col are thus somewhat misnamed, and are basically start and end.

In-place addition

done_tasks[job_index] = done_tasks[job_index] + 1

should be

done_tasks[job_index] += 1

Summation with generators

 profit = 0 
 for job_index in range(0, len(subset)):
 if tasks_to_complete[job_index] == done_tasks[job_index]:
 profit = profit + profits_for_job[job_index]
 

can be

profit = sum(
 profits_for_job[job_index]
 for job_index in range(len(subset))
 if tasks_to_complete[job_index] == done_tasks[job_index]
)

This raises another point, though. Consider "rotating" your data structure so that, instead of multiple sequences where the same index in each correspond to a description of the same thing, e.g.

profits_for_job[job_index]
tasks_to_complete[job_index]
done_tasks[job_index]

instead have a sequence of @dataclasses with attributes:

job[job_index].profits
job[job_index].tasks_to_complete
job[job_index].tasks_done

Predicate combination

 if items_starts[job_index] >= machine_starts[job_index]:
 if items_ends[job_index] <= machine_ends[job_index]:
 done_tasks[job_index] = done_tasks[job_index] + 1

can just be

if (
 items_starts[job_index] >= machine_starts[job_index] and
 items_ends[job_index] <= machine_ends[job_index]
):
 done_tasks[job_index] += 1

• Akash V Patel: The indexing is based on getting a ordered list into subsets of the list.
• Reinderien: That's fine; I still think the variable names could be changed to be less misleading.
• user228914: I'm in the process of writing a review, I see this, and I realize almost all of my points are mentioned here 😂