Python methods to reduce running times KTNS algorithm
1. Bug

The code in the post does not compute the correct sequence of tool insertions for the Keep Tool Needed Soonest (KTNS) algorithm.

This is easiest to see if we print out the tools in the machine at each stage, by adding a line like

print(numpy.nonzero(J)[0] + 1)


near the end of the main loop. The first three lines of output are:

[ 1  2  4 10]
[1 4 5 8]
[1 5 6 9]


The third job in the schedule is job 4, which requires tools number 1, 5, and 9. So why did the code insert tool number 6? This is not needed by job 4, and so according to the KTNS algorithm it should not be inserted into the machine. Something has gone wrong.

This bug causes KTNS to return the wrong result for the example: it returns a cost of 17, but the KTNS algorithm only requires 16 tool insertions for this schedule.

2. Argument

I started to write a review of the code in the post, but the major problem is that the wrong data structures have been selected, so I think it will be more helpful to explain how to approach this kind of problem from first principles.

Tang and Denardo (1986) give a mathematical description of KTNS procedure in section 3 of their paper. Mathematical notation is used in scientific papers because of its compactness and lack of ambiguity. But that doesn't mean that it is a good idea to translate the notation directly into source code. Before writing code, you need to solve two problems:


Choosing good names for variables. In the context of a paper, if you don't know what \$L(i, n)\$ is supposed to mean, then you can refer to its formal definition


  \$L(i, n) = \min\left\{m:m∈T(i, n)\right\}\$


or to its informal description:


  the integer \$L(i, n)\$ is the first instant at or after instant \$n\$ at which tool \$i\$ is needed.


But in the context of source code it is not so easy to refer to these definitions, and so naming a variable Lin is only helpful to the reader who is following along with a copy of the paper. It is better to choose variable names that directly communicate the meaning, and to add comments (if necessary) to make that meaning unambiguous, for example:

# Mapping from tool to the next instant at which it will be needed.
next_needed = { ... }

Choosing data structures. The mathematical notation \$L(i, n)\$ doesn't give any clues as to how this should be implemented. Should you precompute a table of values for all tools \$i\$ and instants \$n\$? Or should you store for each tool the instants where that tool is needed in a sorted list and use bisection to find the first instant at or after \$n\$? Or should you store for each tool the instants where that tool is needed in a sorted queue, and pop its queue when a tool is used, so that the first element of queue is always the next instant when the tool will be needed? Or what? The choice of data structure is vital both in getting the most efficient implementation and in making the code simple and clear to the reader.


3. Decode

The key to finding the best data structures is to have a high level understanding of the algorithm, so that you are not trapped by the notation. The idea is to read the mathematics and decode it into concepts that you can work with. So when the paper says "Set \$J_i = 1\$" you figure out that this means "Insert tool \$i\$ into the machine".

This is the procedure:


  Step 1. Set \$J_i = 1\$ for \$C\$ values of \$i\$ having minimal values of \$L(i, 0)\$. Break the ties arbitrarily. Set \$J_i = 0\$ for the remaining \$M - C\$ values of \$i\$. Set \$n = 1\$.
  
  Step 2. Set \$W_n = J\$. Stop if \$n = N\$.
  
  Step 3. If each \$i\$ having \$L(i, n) = n\$ also has \$J_i = 1\$, set \$n = n + 1\$ and go to Step 2.
  
  Step 4. Pick \$i\$ having \$L(i, n) = n\$ and \$J_i = 0\$. Set \$J_i = 1\$.
  
  Step 5. Set \$J_k = 0\$ for a \$k\$ that maximizes \$L(p, n)\$ over \$\{p: J_p = 1\}\$. Go to Step 3.


Here are my thoughts as I read the procedure:


Steps 2 to step 5 are a loop over \$n\$.
\$n\$ represents the current instant (job) in the schedule.
\$n\$ starts at 1 (the first job) and goes up to \$N\$ (the last job). When implementing this in code, we will need to change this so that instants run from 0 up to (but not including) \$N\$, to avoid having to subtract 1 all the time.
Step 1 is initialization: we fill the machine with the tools that will needed the soonest.
In step 2, \$W_n = J\$ is just recording the set of tools that are now in the machine, which we don't care about since we are only going to be computing the cost.
Step 3 is asking "does the machine contain every tool that is needed by the current job?" If so, it can go on to the next job.
Step 4 only gets run if the machine lacks some tools that are needed. So we pick one of them, tool \$i\$, and insert it into the machine.
Step 5 picks a tool in the machine that is not currently needed and removes it from the machine. The tool is the one that won't be needed for the longest.


4. Pseudo-code

Now that you have a good high-level understanding of the algorithm, the next step is to describe it in pseudo-code. Something like this:


While the machine is under capacity:


Insert the tool that is needed soonest.

For each job in the schedule:


For each tool needed by the job:


Insert the tool into the machine.

While the machine is over capacity:


Remove the tool that won't be needed for the longest.




5. Data structures

Now examine the pseudo-code and figure out the data structures that are needed.


During initialization (but not afterwards), we need to be able to find the tool that is needed soonest.
We need to store the collection of tools that are currently in the machine. 
We need to be able to find the size of this collection, so that we can determine whether the machine is over or under capacity.
This collection needs to support efficient insertion and deletion.
We need to be able to efficiently find the tool in the machine that won't be needed for the longest.


Point 1 is easy enough: for each tool, we can find the jobs that require that tool, and so find the first job for each tool, and use heapq.nsmallest to pick the tools we want.

But points 2 to 5 are hard to satisfy. Here are three alternative implementation strategies:


The requirement to repeatedly and efficiently extract the minimum or maximum element (point 5) suggests some kind of priority queue. In the Python standard library the closest thing we have to a priority queue is a heap and heaps don't support efficient deletion. However, there is a workaround for deleting items from heaps, namely to leave the item in the heap but mark it as deleted, and ignore deleted items when they are extracted. But in order to satisfy point 3 we would need to ignore the deleted items so we would need to maintain a separate count.
Use a data structure from a third-party library. It looks as if a SortedSet from the sortedcontainers library would meet our requirements.
Use an ordinary data structure like a set, and accept some inefficiency in point 5 by calling max (taking time proportional to the capacity of the machine). When the capacity is small, this is acceptable.


I'm going to use strategy 3 because it's the simplest and because in your example the capacity is 4, which is small enough for the inefficiency not to matter.

6. Implementation

from collections import defaultdict, deque
from heapq import nsmallest

def schedule_cost(schedule, requirements, capacity):
    """Return the cost of the schedule, that is, the number of tool insertions.

    Parameters:
    schedule -- Sequence of jobs.
    requirements -- Mapping from job to iterable of required tools.
    capacity -- Number of tools that the machine can hold at once.

    Jobs and tools may be any hashable objects.

    """
    # Mapping from tool to deque of instants when the tool will be needed.
    tool_instants = defaultdict(deque)
    for i, job in enumerate(schedule):
        assert len(requirements[job]) &lt;= capacity
        for tool in requirements[job]:
            tool_instants[tool].append(i)
    for instants in tool_instants.values():
        instants.append(len(schedule))

    # Point in schedule when tool will next be needed.
    def next_needed(tool):
        return tool_instants[tool][0]

    # Set of tools in the machine.
    machine = set(nsmallest(capacity, tool_instants, key=next_needed))

    cost = len(machine)
    for job in schedule:
        # Set of tools that need to be inserted.
        new_tools = {tool for tool in requirements[job] if tool not in machine}
        if new_tools:
            cost += len(new_tools)
            # Remove tools if necessary to avoid going over capacity.
            for _ in range(len(machine) + len(new_tools) - capacity):
                machine.remove(max(machine, key=next_needed))
            machine.update(new_tools)
        for tool in requirements[job]:
            tool_instants[tool].popleft()

    return cost


7. Performance

The revised code in §6 is about 20 times faster than the code in the post:

&gt;&gt;&gt; test = lambda:schedule_cost([10, 9, 4, 1, 6, 3, 7, 5, 2, 8], J, 4)
&gt;&gt;&gt; from timeit import timeit
&gt;&gt;&gt; KTNS()[1] / timeit(test, number=1)
20.335097001763668


8. Tool decisions

If you also want to return the decisions about which tools to insert (in addition to the cost), then that's easy. The newly inserted tools at each instant are in the new_tools set, and the tools in the machine at each instant are in the machine set. Take a copy of whichever one of these you need to keep.

For example, if you want to keep copies of machine then you would start with something like:

machine_record = []


and then at the end of each loop, append a copy of machine to the record:

machine_record.append(set(machine))


and findally return the record along with the cost:

return cost, machine_record