Finding sum-free partitions
Python 3, sort by greatest number, n = 92 121
Thanks to Martin Büttner for a suggestion that unexpectedly improved the maximum n reached.
Last output:
[2, 3, 11, 12, 29, 30, 38, 39, 83, 84, 92, 93, 110, 111, 119, 120]
[1, 4, 10, 13, 28, 31, 37, 40, 82, 85, 91, 94, 109, 112, 118, 121]
[5, 6, 7, 8, 9, 32, 33, 34, 35, 36, 86, 87, 88, 89, 90, 113, 114, 115, 116, 117]
[14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108]
[41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81]

The algorithm is the same as my previous answer, quoted below:

There are k bins that have both the numbers in it so far and the numbers that can't go in it anymore. At each depth in the iteration (it's basically a depth-first search), the bin ordering is shuffled and the next number (nextN) is (sequentially) put into the bins that can take it and then goes one step deeper. If there are none, it returns, backing up one step.

...with one exception: the bin ordering is not shuffled. Instead, it is sorted in such a way that the bins with the greatest number come first. This reached n = 121 in 8 seconds!
Code:
from copy import deepcopy
from random import shuffle, seed
from time import clock, time
global maxN
maxN = 0
clock()

def search(k,nextN=1,sets=None):
    global maxN
    if clock() &gt; 600: return
    
    if nextN == 1: #first iteration
        sets = []
        for i in range(k):
            sets.append([[],[]])

    sets.sort(key=lambda x:max(x[0]or[0]), reverse=True)
    for i in range(k):
        if clock() &gt; 600: return
        if nextN not in sets[i][1]:
            sets2 = deepcopy(sets)
            sets2[i][0].append(nextN)
            sets2[i][1].extend([nextN+j for j in sets2[i][0]])
            nextN2 = nextN + 1
            
            if nextN &gt; maxN:
                maxN = nextN
                print(&quot;New maximum!&quot;,maxN)
                for s in sets2: print(s[0])
                print(time())
                print()
                
            search(k, nextN2, sets2)

search(5)