fcmaes - a Python 3 gradient-free optimization library

This tutorial:

Uses continuous optimization and numba to solve the Flexible job shop problem (FJSP).
Shows that on modern many-core CPUs, generic optimization can often replace dedicated algorithms while still delivering good results.
Has practical advantages:
- Easy to implement.
- Easy to adapt to additional constraints, objectives, or noise.
Demonstrates this flexibility with a problem variant for asteroid harvesting.

Solving the flexible job shop scheduling problem using continuous optimization

Production scheduling assigns available resources to tasks. It also determines an execution order that satisfies all constraints while optimizing one or more objectives.

In the Flexible job shop problem (FJSP), we must choose a machine for each operation and decide the order of operations on the machines. These decisions are usually called machine selection and operation sequencing. Typical goals are to minimize makespan, maximum tardiness, and related indicators.

Many commercial tools can solve this kind of problem, including CP and LocalSolver and Gurobi. Here we focus on something these tools handle less naturally: multiple objectives and the computation of a Pareto front. A Pareto front is a set of solutions where improving one objective necessarily worsens another. In practice, it gives a set of trade-off choices. With ILOG_CP you can formulate multiple objectives, but you must prioritize them in advance.

We also cover the single-objective case. That matters if you do not have a commercial solver available. The approach shown here can also help on very large instances, where the number of constraints handled by ILOG_CP can grow quickly. We use the highly efficient optimizers MoDe and BiteOpt implemented in C++.

The full Python code for this tutorial is here: jobshop.py and here: harvesting.py

We also show how to handle:

additional constraints, such as the maximal number of machines that may be active at a given time.
relaxations, such as replacing strict sequence ordering by an acyclic graph.

Using continuous optimization for a problem with discrete decisions may look unusual, but it is a common approach. See for instance overview 1 or overview 2. One reason is that the indirect encoding of real-valued parameters can resolve constraints in a flexible and efficient way.

Indirect Encoding

A decoder maps the encoded parameters to a solution expressed by a vector of continuous variables. The decoder handles the constraints of the optimization problem and guarantees that the decoded solution is valid.

Consider the sequence constraint. For each job, the execution order of the operations is determined by the part of the continuous input vector x extracted by x[n_operations:]. We first apply the numpy argsort operator. It returns integer values that describe the order of its input.

order = np.argsort(x[n_operations:])

The actual decoding step is performed by reorder. It avoids an expensive nested loop. job_ids and job_indices look like 1,1,1,2,2,2,2,3,3,… and 0,3,7,….

@njit(fastmath=True)
def reorder(tasks, order, n_operations, job_ids, job_indices):
    ids = job_ids[order]
    ordered = np.empty((n_operations,4))
    op_index = np.zeros(n_operations, dtype=numba.int32)
    for i in range(n_operations):
        machine = ids[i]
        index = job_indices[machine] + op_index[machine]
        op_index[machine] += 1
        ordered[i] = tasks[index]
    return ordered

An encoder that enforces the full constraint also makes it easy to relax that constraint. If we enforce only a partial order order_relation, we need a nested loop, so we rely on Numba to keep it fast.

@njit(fastmath=True)
def reorder(tasks, order_relation):
    n = tasks.shape[0]
    for i in range(n):
        for j in range(i+1, n):
            if tasks[i][0] == tasks[j][0]: # same job
                if not order_relation(tasks[i][1], tasks[j][1]): # swap if task order doesn't fit
                    tasks[i], tasks[j] = tasks[j].copy(), tasks[i].copy()
    return tasks

Objective function

We can now state the flexible job shop problem more precisely:

A set of jobs must be processed on a set of machines without interruption. Each job is a sequence of consecutive operations. Each operation can run on a specific set of machines, and its execution time depends on the chosen machine. Machines are continuously available and can process one operation at a time. A solution consists of both a schedule and an operation-machine assignment.

Here is a solution for Brandimartes first benchmark instance (which can be downloaded here Kefalas).

Colors represent jobs, and the numbers identify operations. As expected, the operations of each job are executed sequentially. Running the tutorial code jobshop.py produces a similar Gantt diagram from a freshly computed solution.

We use the following objectives:

makespan: maximum of the completion time for all jobs
total workload: sum of the execution time for all operations
maximum workload: maximum of the overall execution time for all machines

as in Honda. This paper can also be found at Kefalas, together with their Python implementation, results, and the problem instances we use for comparison. Compared to their implementation, ours is more focused on efficiency, meaning the number of function evaluations performed per second.

As a user, you care about result quality within a fixed amount of time. If one implementation is 20x faster but needs 10x more evaluations, it still reaches a result about twice as fast. Both implementations rely on Python multithreading, but the scaling differs a lot because we parallelize whole optimizations, not individual objective evaluations. That reduces the number of processes created and destroyed and lowers overhead. We also use Numba, so the objective function is written in terms of vectors (numpy arrays) instead of classes or objects.

Implementation

We first convert the problem into a list of 4-tuples: (job-id, operation-id, machine-id, execution-time). The ids are integers and the execution time is a float. Each possible machine assignment for a given job/operation becomes a separate tuple, and these tuples are stored consecutively.

The objective function performs four steps:

1) Filter tuples so that only one machine assignment per job/operation is kept. The selection is performed according to the input vector.

2) Reorder the filtered list according to the input vector while maintaining the sequence constraint.

3) Execute the operations represented by the final tuple list in the given order. The assigned machine is used as soon as it becomes available and the previous operation of the same job has completed.

4) Collect the objective values.

In the Python code (see jobshop.py) this looks as follows:

    # step 1 + 2
    tasks = filtered_tasks(x, self.task_data, self.n_operations, self.n_machines,
                           self.job_indices, self.job_ids)
    # step 3
    machine_time, job_time, machine_work_time = exec_tasks(tasks, self.n_jobs, self.n_machines)
    # step 4
    span = np.amax(machine_time)
    work = np.sum(machine_work_time)
    wmax = np.amax(machine_work_time)

Steps 1 and 2 are combined in filtered_tasks.

    @njit(fastmath=True)
    def filtered_tasks(x, task_data, n_operations, n_machines, job_indices, job_ids):
        # step 1
        operations = filter_tasks(x, task_data, n_operations, n_machines)
        order = np.argsort(x[n_operations:])
        # step 2
        tasks = reorder(operations, order, n_operations, job_ids, job_indices)
        return tasks

Execution of the resulting list of operations, called tasks, is straightforward. We track the current finish time for each machine and each job. We also accumulate the execution time for each machine.

    @njit(fastmath=True)
    def exec_tasks(tasks, n_jobs, n_machines):
        machine_time = np.zeros(n_machines)
        machine_work_time = np.zeros(n_machines)
        job_time = np.zeros(n_jobs)
        for task in tasks:
            job = int(task[0])
            machine = int(task[2])
            time = task[3]
            # previous task needs to be finished and machine needs to be available
            end_time = max(machine_time[machine], job_time[job]) + time
            machine_time[machine] = end_time
            job_time[job] = end_time
            machine_work_time[machine] += time
        return machine_time, job_time, machine_work_time

For single-objective optimization, we call the multi-objective function fun and combine its outputs with a weighted sum:

   def __call__(self, x): # single objective function
        ys = self.fun(x)
        return sum(self.weights*ys) # weighted sum

For multi-objective optimization, we use MoDe implemented in C++. We call it through the parallel retry mechanism:

    xs, front = modecpp.retry(fit.fun, fit.nobj, fit.ncon, fit.bounds, num_retries=32, popsize = 48,
              max_evaluations = 960000, nsga_update = True, logger = logger(), workers=16)
    logger().info(name + " modecpp.retry(num_retries=32, popsize = 48, max_evals = 960000, nsga_update = True, workers=16" )
    logger().info(str([tuple(y) for y in front]))

To collect optimization results, the parallel retry stores the Pareto front computed by each run in mode.store. A multiprocessing.Lock enables safe parallel access.

MoDe provides two population update mechanisms: one derived from NSGA-II and one from DE. Experiments have shown that the NSGA-II-style update works better for this application. Even in that configuration, the algorithm still differs significantly from standard NSGA-II. There is no tournament selection, and MoDe can handle constraints.

For single objective optimization BiteOpt from Aleksey Vaneev works very well. Parallel optimization is already covered by fcmaes.retry.

    store = retry.Store(fit, bounds, logger=logger())
    logger().info(name + " Bite_cpp(960000,M=1).minimize, num_retries=256)" )
    retry.retry(store, Bite_cpp(960000,M=1).minimize, num_retries=256)

Asteroid harvesting

We implemented a variation of FJSP in harvesting.py to show how easily additional constraints can be added. The scenario is motivated by the gradual depletion of resources on Earth. One possible long-term idea is to harvest resources, and produce goods from them, on asteroids. This leads to the following simplified problem:

N movable identical factories are deployed on N asteroids to perform operations associated with m jobs. As in FJSP, the operations must be executed in the order specified by the job. The counterpart of a machine in FJSP is a factory deployment to a specific asteroid. The resources on that asteroid determine which job operations can be executed there. In this simplified model, asteroid harvesting can be viewed as an FJSP with two additional constraints:

Moving factories is expensive, so a factory can only be deployed once on an asteroid. It is active for a single consecutive time window.
The upper limit of active machines, or factory deployments, is determined by N, the number of factories.

Here is a solution for Brandimartes first benchmark problem instance with an upper limit of 4 active factories.

Running the tutorial code harvesting.py produces a similar Gantt diagram from a freshly computed solution.

These constraints are not new. With ILOG CP, you can express them and compute a solution. Our focus is again the multi-objective variant of the problem.

Implementation

Compared to the FJSP implementation above, the main difference is that we have 2*n_machines+1 additional input variables:

The upper time limit for which any machine or factory can be active (max_time).
The start time at which each machine is activated, meaning the factory is moved to the corresponding asteroid (start).
The duration for which each machine remains active, meaning the factory stays at the asteroid (duration).

    max_time = x[-1]
    start = x[-self.n_machines-1:-1]*max_time
    duration = x[-2*self.n_machines-1:-self.n_machines-1]*max_time
    machine_time, job_time, machine_work_time, fails = \
        exec_tasks(tasks, self.n_jobs, self.n_machines, self.max_active, start, duration)
    if fails is None: # timing error
        return np.array([0, 0, 0, 10000])

exec_tasks now calls adjust_timing as part of the constraint-enforcing parameter encoding. adjust_timing shifts the timing so that the max_active constraint is satisfied:

@njit(fastmath=True)
def exec_tasks(tasks, n_jobs, n_machines, max_active, start, duration):
    success, start, stop = adjust_timing(start, duration, max_active)
    if not success:
        return None, None, None, None
    ...
    return machine_time, job_time, machine_work_time, fails

adjust_timing may fail. In that case, the objective function returns a very high value to guide the optimization toward valid timings.
There is an additional return value fails counting the number of operations that cannot be executed. This happens when the selected machine is already shut down, meaning the factory moved to another asteroid.

    end_time = max(machine_time[machine], job_time[job]) + time
    if end_time > stop[machine]: # machine already shut down
        fails += 1 # failure to execute task at all

fails should not be treated like an ordinary objective, because all solutions with fails > 0 are invalid. Reducing fails must be prioritized by the optimization process. Luckily modecpp.minimize supports constraints as a special kind of objective.

After calling modecpp.retry we filter infeasible results:

def retry_modecpp(fit, retry_num = 32, popsize = 48, max_eval = 500000,
                  nsga_update = True, logger = logger(), workers=mp.cpu_count()):
    xf, yf = modecpp.retry(fit.fun, fit.nobj, fit.ncon, fit.bounds, retry_num, popsize,
                  max_evaluations = 960000, nsga_update = nsga_update, logger = logger, workers=workers)
    xs = []; ys = []
    for i in range(len(yf)):
        if yf[i][-1] == 0: # filter valid solutions
            xs.append(xf[i])
            ys.append(yf[i][:fit.nobj])
    return np.array(xs), np.array(ys)

and declare the new quantity as a constraint:

class fitness:

    def __init__(self, task_data, bounds, n_jobs, n_operations, n_machines, max_active, name):
        ...
        self.nobj = 3
        self.ncon = 1
        ...

Of course this does not work for single-objective optimization. There we assign a high weight to the constraint:

self.weights = np.array([1, 02, 001, 1000]) # only used for single objective optimization

Results

All results can be reproduced by executing:

    optall(multi_objective = True)

For FJSP we can compare with Results_TSM.txt from Kefalas. Unfortunately, no timings are given there. We tried to reproduce their results using the Python code but got slightly worse values, probably because of a parameterization issue.

There do not seem to be results in the literature for Mk11-15, probably because these benchmarks are hard to find. Luckily they are included in Kefalas.

Our timings were produced on a 16-core AMD 5950x CPU using 16 threads. Hyperthreading (workers= mp.cpu_count()) only helps for the single-objective optimization with BiteOpt.

Results
===============

Mk01: Results_TSM.txt from https://moda.liacs.nl/code/KefalasEtAl2019-Supplement.zip

[(40, 168, 37),  (40, 174, 36),  (41, 167, 36),  (41, 162, 39),  (41, 165, 37),  (41, 164, 38),  (42, 159, 39),  (42, 160, 38),  (42, 163, 37),  (42, 165, 36),  (43, 155, 40),  (43, 158, 39),  (44, 154, 40),  (46, 153, 42)]

Mk01: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 49.3s

[(40, 165, 37), (40, 167, 36), (41, 162, 38), (41, 163, 37), (41, 160, 39), (42, 160, 38), (42, 165, 36), (42, 157, 40), (42, 158, 39), (43, 155, 40), (44, 154, 40), (46, 153, 42)]


================
Mk02: Results_TSM.txt from https://moda.liacs.nl/code/KefalasEtAl2019-Supplement.zip

[(29, 150, 26),  (29, 144, 28),  (29, 145, 27),  (30, 143, 29),  (31, 141, 31),  (31, 142, 30),  (33, 140, 33)]

Mk02: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 48.3s

[(27, 150, 27), (27, 153, 26), (28, 151, 26), (28, 145, 28), (28, 146, 27), (29, 145, 27), (29, 143, 29), (29, 144, 28), (29, 150, 26), (31, 141, 31), (31, 142, 30), (33, 140, 33)]


================
Mk03: Results_TSM.txt from https://moda.liacs.nl/code/KefalasEtAl2019-Supplement.zip

[(204, 864, 204),  (206, 857, 204),  (210, 855, 204),  (213, 852, 204),  (215, 849, 213),  (216, 848, 213),  (222, 847, 222),  (223, 847, 213),  (224, 851, 204),  (226, 843, 222),  (230, 842, 222),  (234, 846, 213),  (237, 844, 213),  (240, 850, 204),  (246, 841, 231),  (247, 849, 210),  (248, 848, 210),  (249, 840, 249),  (256, 838, 249),  (256, 840, 222),  (262, 838, 231),  (274, 839, 222),  (275, 838, 222),  (282, 837, 231),  (297, 843, 221)]

Mk03: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 64.8s

[(204, 852, 204), (205, 850, 204), (211, 848, 210), (213, 844, 213), (221, 842, 221), (222, 838, 222), (231, 834, 231), (240, 832, 240), (249, 830, 249), (258, 828, 258), (267, 826, 267), (276, 824, 276), (285, 822, 285), (294, 820, 294), (303, 818, 303), (312, 816, 312), (321, 814, 321), (330, 812, 330)]


=================
Mk04: Results_TSM.txt from https://moda.liacs.nl/code/KefalasEtAl2019-Supplement.zip

[(68, 355, 68),  (68, 376, 60),  (69, 360, 60),  (69, 351, 63),  (71, 353, 62),  (72, 347, 66),  (72, 357, 61),  (73, 342, 72),  (73, 348, 63),  (75, 344, 66),  (75, 347, 65),  (77, 340, 72),  (78, 337, 78),  (79, 343, 67),  (84, 334, 84),  (90, 331, 90),  (98, 330, 98),  (106, 329, 106),  (114, 328, 114),  (122, 327, 122),  (130, 326, 130),  (138, 325, 138),  (146, 324, 146)]

Mk04: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 53.6s

[(63, 374, 60), (63, 371, 61), (64, 368, 60), (64, 365, 61), (64, 362, 62), (65, 359, 61), (65, 360, 60), (66, 353, 62), (66, 357, 61), (67, 350, 66), (68, 347, 68), (68, 351, 63), (68, 348, 66), (69, 347, 66), (69, 350, 63), (69, 346, 68), (70, 346, 66), (70, 349, 63), (71, 347, 65), (71, 344, 66), (71, 348, 63), (72, 341, 72), (72, 343, 67), (73, 340, 72), (78, 337, 78), (84, 334, 84), (90, 331, 90), (98, 330, 98), (106, 329, 106), (114, 328, 114), (122, 327, 122), (130, 326, 130), (138, 325, 138), (146, 324, 146)]


==================
Mk05: Results_TSM.txt from https://moda.liacs.nl/code/KefalasEtAl2019-Supplement.zip

[(174, 687, 173),  (176, 686, 173),  (177, 685, 173),  (178, 683, 175),  (178, 682, 176),  (179, 684, 174),  (179, 680, 179),  (180, 682, 175),  (180, 681, 178),  (181, 684, 173),  (181, 679, 179),  (181, 680, 178),  (182, 683, 173),  (182, 687, 172),  (183, 677, 183),  (185, 676, 185),  (191, 675, 191),  (197, 674, 197),  (203, 673, 203),  (209, 672, 209)]

Mk05: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 56.5s

[(173, 685, 173), (174, 683, 174), (174, 684, 173), (175, 682, 175), (175, 687, 172), (175, 683, 173), (178, 680, 178), (179, 679, 179), (183, 677, 183), (185, 676, 185), (191, 675, 191), (197, 674, 197), (203, 673, 203), (209, 672, 209)]


==================
Mk06: Results_TSM.txt from https://moda.liacs.nl/code/KefalasEtAl2019-Supplement.zip

[(91, 474, 57),  (91, 453, 66),  (92, 436, 60),  (93, 480, 54),  (95, 456, 55),  (96, 434, 60),  (96, 428, 61),  (99, 432, 60),  (99, 427, 71),  (100, 476, 54),  (100, 450, 57),  (102, 455, 54),  (103, 452, 54),  (103, 446, 59),  (104, 451, 54),  (105, 449, 55),  (106, 420, 74),  (107, 423, 63),  (108, 421, 69),  (108, 447, 56),  (109, 421, 66),  (109, 441, 59),  (110, 442, 55),  (110, 421, 60),  (112, 417, 67),  (113, 411, 74),  (115, 414, 68),  (115, 415, 63),  (122, 439, 56),  (124, 418, 60),  (124, 412, 67),  (125, 450, 54),  (126, 417, 60),  (129, 437, 57),  (130, 434, 58),  (131, 440, 55),  (131, 413, 63),  (136, 449, 54),  (139, 407, 69),  (140, 444, 54),  (141, 438, 56),  (141, 439, 55),  (142, 411, 65),  (143, 402, 82),  (144, 406, 67),  (154, 434, 54),  (158, 473, 53)]

Mk06: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 66.2s

[(68, 395, 61), (69, 386, 62), (70, 380, 67), (70, 381, 65), (71, 383, 63), (71, 377, 70), (71, 379, 68), (72, 381, 64), (72, 374, 69), (72, 377, 67), (72, 375, 68), (73, 383, 61), (73, 379, 63), (73, 373, 70), (73, 374, 68), (73, 372, 71), (74, 380, 62), (74, 407, 57), (74, 375, 67), (74, 403, 59), (74, 368, 69), (74, 382, 60), (74, 367, 70), (75, 366, 72), (75, 403, 57), (75, 365, 73), (75, 377, 63), (75, 373, 65), (75, 372, 66), (75, 396, 58), (76, 369, 67), (76, 370, 66), (77, 368, 66), (77, 365, 70), (77, 393, 59), (77, 378, 62), (77, 364, 71), (77, 358, 76), (77, 366, 69), (78, 376, 62), (78, 360, 73), (78, 363, 71), (78, 358, 75), (78, 364, 70), (78, 375, 63), (78, 365, 69), (78, 366, 68), (78, 378, 61), (78, 374, 64), (79, 353, 78), (79, 374, 63), (79, 361, 72), (79, 362, 71), (79, 358, 74), (79, 356, 76), (79, 359, 73), (80, 379, 60), (80, 372, 64), (80, 355, 77), (80, 371, 65), (80, 357, 74), (81, 355, 76), (81, 354, 77), (81, 352, 78), (82, 356, 75), (82, 390, 59), (82, 350, 81), (82, 351, 80), (83, 348, 82), (83, 353, 77), (83, 350, 80), (83, 349, 81), (83, 365, 68), (83, 363, 70), (84, 347, 82), (84, 375, 62), (84, 348, 81), (84, 351, 79), (84, 373, 63), (85, 360, 72), (85, 376, 61), (86, 350, 79), (86, 344, 85), (86, 346, 83), (87, 371, 64), (87, 343, 85), (87, 344, 84), (88, 342, 87), (89, 346, 82), (89, 341, 87), (89, 342, 86), (89, 340, 88), (90, 339, 90), (91, 338, 90), (91, 339, 88), (92, 337, 91), (93, 336, 93), (93, 337, 90), (94, 336, 91), (94, 335, 94), (95, 335, 93), (96, 334, 94), (97, 333, 96), (98, 332, 97), (100, 331, 99), (101, 330, 100)]

==================
Mk07: Results_TSM.txt from https://moda.liacs.nl/code/KefalasEtAl2019-Supplement.zip

[(144, 690, 144),  (148, 685, 144),  (150, 690, 143),  (150, 684, 149),  (153, 680, 150),  (153, 683, 147),  (154, 673, 150),  (156, 682, 147),  (157, 683, 145),  (157, 691, 142),  (158, 670, 156),  (158, 679, 145),  (158, 690, 140),  (160, 675, 147),  (160, 671, 150),  (160, 677, 144),  (161, 673, 144),  (162, 668, 156),  (163, 666, 162),  (163, 667, 157),  (166, 664, 157),  (166, 670, 150),  (168, 689, 142),  (169, 688, 141),  (169, 663, 162),  (170, 662, 157),  (171, 661, 169),  (172, 667, 156),  (172, 687, 143),  (174, 688, 140),  (175, 686, 140),  (176, 660, 174),  (178, 668, 152),  (179, 657, 170),  (182, 684, 143),  (185, 665, 156),  (191, 660, 169),  (192, 661, 162),  (193, 659, 162),  (194, 655, 190),  (197, 655, 176),  (206, 653, 202),  (220, 658, 166),  (221, 654, 190),  (227, 653, 187),  (241, 652, 209),  (244, 657, 166),  (265, 651, 209),  (268, 651, 205),  (277, 652, 202)]

Mk07: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 55.5s

[(141, 688, 141), (142, 686, 140), (143, 684, 143), (143, 685, 142), (144, 673, 144), (144, 683, 143), (150, 669, 150), (151, 667, 151), (151, 685, 140), (156, 664, 156), (157, 662, 157), (161, 660, 161), (162, 659, 162), (166, 657, 166), (175, 655, 175), (187, 653, 187), (202, 651, 202), (217, 649, 217)]

===================
Mk08: Results_TSM.txt from https://moda.liacs.nl/code/KefalasEtAl2019-Supplement.zip

[(523, 2524, 523),  (524, 2519, 524),  (533, 2514, 533),  (542, 2509, 542),  (551, 2504, 551),  (560, 2499, 560),  (569, 2494, 569),  (578, 2489, 578),  (587, 2484, 587)]

Mk08: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 79.7s

[(523, 2524, 523), (524, 2519, 524), (533, 2514, 533), (542, 2509, 542), (551, 2504, 551), (560, 2499, 560), (569, 2494, 569), (578, 2489, 578), (587, 2484, 587)]


===================
Mk09: Results_TSM.txt from https://moda.liacs.nl/code/KefalasEtAl2019-Supplement.zip time = 55.5s

[(369, 2711, 328),  (372, 2493, 310),  (373, 2452, 299),  (377, 2415, 300),  (379, 2396, 299),  (386, 2375, 320),  (389, 2387, 299),  (393, 2365, 315),  (394, 2376, 299),  (396, 2368, 299),  (399, 2364, 307),  (401, 2336, 331),  (401, 2364, 299),  (410, 2340, 316),  (414, 2361, 315),  (419, 2352, 304),  (424, 2361, 299),  (427, 2359, 300),  (427, 2360, 299),  (432, 2341, 299),  (448, 2331, 328),  (468, 2322, 307),  (493, 2339, 299),  (507, 2338, 303),  (523, 2338, 299),  (534, 2335, 301),  (543, 2311, 320),  (559, 2321, 310),  (563, 2335, 299),  (567, 2327, 299)]

Mk09: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 81.7s

[(334, 2271, 307), (335, 2269, 310), (335, 2263, 316), (335, 2272, 304), (335, 2270, 307), (336, 2267, 309), (337, 2259, 316), (337, 2268, 307), (338, 2262, 310), (338, 2267, 307), (339, 2254, 323), (339, 2261, 315), (340, 2260, 315), (342, 2266, 307), (342, 2261, 312), (343, 2256, 316), (343, 2251, 326), (344, 2250, 323), (344, 2261, 310), (344, 2258, 312), (344, 2253, 315), (344, 2264, 309), (345, 2247, 326), (346, 2246, 326), (347, 2244, 323), (347, 2257, 312), (347, 2251, 321), (348, 2242, 326), (349, 2260, 310), (350, 2255, 314), (351, 2240, 327), (351, 2249, 320), (351, 2256, 312), (353, 2239, 328), (354, 2237, 348), (354, 2246, 321), (354, 2245, 322), (355, 2238, 333), (355, 2264, 308), (355, 2235, 334), (356, 2237, 332), (356, 2233, 348), (357, 2231, 340), (357, 2238, 331), (358, 2241, 326), (358, 2230, 348), (359, 2234, 334), (359, 2229, 342), (360, 2235, 333), (361, 2236, 332), (361, 2232, 339), (361, 2228, 348), (362, 2228, 346), (363, 2227, 346), (363, 2225, 348), (363, 2230, 340), (364, 2226, 346), (364, 2231, 339), (365, 2223, 364), (367, 2224, 354), (370, 2222, 370), (370, 2225, 347), (371, 2223, 354), (373, 2224, 353), (373, 2222, 360), (373, 2221, 370), (374, 2224, 348), (374, 2252, 316), (376, 2220, 376), (376, 2221, 366), (378, 2222, 355), (379, 2221, 364), (381, 2221, 360), (381, 2220, 366), (381, 2219, 376), (384, 2219, 375), (386, 2218, 386), (387, 2218, 382), (392, 2217, 392), (393, 2217, 388), (398, 2216, 398), (401, 2216, 394), (404, 2215, 404), (414, 2214, 414), (424, 2213, 424), (434, 2212, 434), (444, 2211, 444), (454, 2210, 454)]


===================
Mk10: Results_TSM.txt from https://moda.liacs.nl/code/KefalasEtAl2019-Supplement.zip

[(300, 2157, 224),  (311, 2128, 256),  (313, 2190, 220),  (313, 2127, 242),  (313, 2132, 241),  (314, 2133, 230),  (315, 2156, 220),  (316, 2128, 220),  (317, 2127, 211),  (318, 2113, 239),  (318, 2125, 230),  (321, 2101, 259),  (322, 2122, 223),  (323, 2113, 224),  (324, 2112, 217),  (325, 2094, 220),  (326, 2090, 221),  (331, 2109, 214),  (332, 2171, 210),  (333, 2137, 210),  (335, 2106, 218),  (336, 2087, 233),  (336, 2112, 208),  (339, 2082, 229),  (343, 2109, 213),  (345, 2107, 216),  (353, 2105, 215),  (357, 2082, 220),  (358, 2111, 212),  (359, 2069, 253),  (359, 2091, 208),  (362, 2080, 250),  (362, 2081, 236),  (363, 2057, 242),  (364, 2054, 210),  (364, 2128, 205),  (368, 2115, 206),  (390, 2092, 205),  (397, 2050, 248),  (416, 2084, 206),  (427, 2127, 204),  (452, 2082, 206),  (460, 2078, 209),  (515, 2132, 202)]

Mk10: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 83.0s

[(236, 1899, 218), (237, 1896, 215), (237, 1894, 220), (239, 1893, 215), (239, 1891, 220), (240, 1886, 218), (241, 1881, 220), (242, 1878, 220), (243, 1900, 214), (243, 1901, 210), (244, 1898, 212), (244, 1891, 215), (244, 1876, 225), (245, 1874, 225), (245, 1888, 215), (246, 1882, 215), (246, 1875, 218), (247, 1873, 235), (247, 1908, 209), (248, 1871, 230), (248, 1870, 240), (248, 1874, 220), (248, 1887, 212), (248, 1872, 221), (249, 1881, 216), (249, 1872, 220), (250, 1869, 225), (251, 1879, 215), (251, 1893, 210), (251, 1869, 220), (252, 1877, 216), (252, 1864, 227), (252, 1891, 210), (253, 1899, 209), (254, 1889, 210), (254, 1897, 209), (254, 1863, 235), (254, 1886, 212), (255, 1883, 212), (255, 1877, 215), (255, 1866, 225), (255, 1862, 245), (256, 1904, 208), (256, 1860, 240), (256, 1861, 230), (257, 1895, 209), (257, 1887, 211), (257, 1857, 250), (260, 1859, 236), (261, 1863, 227), (262, 1858, 249), (262, 1856, 260), (262, 1860, 235), (262, 1866, 224), (262, 1863, 225), (263, 1858, 240), (265, 1861, 227), (265, 1857, 240), (265, 1858, 230), (266, 1854, 250), (266, 1856, 236), (267, 1855, 240), (272, 1852, 270), (273, 1858, 228), (273, 1857, 235), (276, 1853, 260), (276, 1855, 230), (276, 1854, 240), (278, 1851, 250), (282, 1903, 208), (283, 1853, 236), (283, 1852, 240), (284, 1850, 260), (284, 1849, 270), (289, 1848, 280), (321, 1847, 290)]


===================

Mk11: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 70.5s

[(610, 3037, 610), (611, 3028, 611), (614, 3027, 614), (617, 3026, 617), (618, 3030, 609), (620, 3029, 610), (620, 3025, 620), (621, 3023, 621), (622, 3027, 611), (623, 3022, 623), (624, 3018, 624), (627, 3017, 627), (633, 3016, 626), (637, 3015, 637), (639, 3011, 639), (640, 3010, 640), (643, 3009, 643), (646, 3008, 646), (650, 3007, 649), (650, 3006, 650), (654, 3002, 654), (660, 3001, 660), (663, 3000, 663), (666, 2999, 666), (669, 2998, 669), (675, 2997, 675), (676, 2994, 676), (682, 2993, 682), (685, 2991, 685), (688, 2990, 688), (698, 2987, 698), (704, 2986, 704), (707, 2984, 707), (720, 2982, 720), (723, 2981, 723), (726, 2979, 726), (742, 2977, 742), (746, 2976, 746), (747, 2975, 747), (764, 2974, 764), (769, 2973, 769), (770, 2972, 770), (791, 2971, 791), (812, 2970, 812), (833, 2969, 833), (854, 2968, 854), (875, 2967, 875)]

===================

Mk12: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 72.6s

[(508, 3325, 508), (516, 3324, 516), (517, 3322, 517), (518, 3307, 518), (524, 3282, 524), (528, 3279, 528), (529, 3264, 529), (539, 3260, 539), (540, 3247, 540), (545, 3245, 545), (556, 3232, 556), (561, 3230, 561), (572, 3217, 572), (577, 3215, 577), (593, 3213, 593), (609, 3211, 609), (625, 3209, 625), (641, 3207, 641), (658, 3205, 658), (675, 3203, 675), (692, 3201, 692), (709, 3199, 709), (726, 3197, 726), (743, 3195, 743)]

===================

Mk13: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 81.3s

[(433, 3719, 418), (435, 3716, 418), (436, 3715, 418), (438, 3714, 426), (439, 3713, 426), (441, 3701, 430), (444, 3682, 426), (447, 3675, 426), (449, 3672, 434), (449, 3667, 442), (450, 3657, 439), (450, 3715, 416), (450, 3671, 434), (453, 3648, 448), (453, 3674, 426), (454, 3657, 438), (455, 3653, 438), (455, 3706, 423), (456, 3669, 432), (458, 3647, 442), (458, 3640, 450), (458, 3668, 426), (460, 3630, 454), (460, 3666, 432), (460, 3703, 416), (462, 3693, 422), (462, 3650, 436), (462, 3665, 426), (463, 3664, 426), (463, 3661, 435), (464, 3637, 449), (465, 3636, 452), (466, 3708, 414), (466, 3646, 442), (467, 3698, 421), (467, 3629, 462), (467, 3661, 426), (468, 3655, 432), (469, 3651, 432), (470, 3638, 438), (471, 3624, 470), (472, 3649, 436), (472, 3618, 470), (473, 3626, 454), (474, 3631, 450), (476, 3687, 424), (477, 3649, 432), (477, 3692, 423), (477, 3616, 470), (479, 3697, 417), (479, 3621, 468), (480, 3674, 419), (480, 3612, 470), (480, 3625, 454), (480, 3623, 467), (481, 3674, 418), (481, 3618, 468), (481, 3624, 454), (483, 3617, 468), (485, 3630, 450), (485, 3636, 449), (486, 3606, 486), (486, 3611, 470), (487, 3605, 486), (492, 3603, 486), (493, 3702, 414), (494, 3602, 486), (496, 3671, 424), (496, 3610, 485), (498, 3598, 488), (499, 3599, 486), (500, 3661, 422), (500, 3652, 431), (502, 3592, 502), (504, 3598, 486), (505, 3671, 419), (506, 3591, 506), (511, 3590, 504), (512, 3589, 504), (514, 3591, 503), (514, 3586, 504), (516, 3585, 509), (518, 3579, 518), (523, 3585, 506), (527, 3578, 524), (527, 3637, 441), (528, 3585, 504), (534, 3572, 534), (535, 3578, 521), (535, 3673, 418), (542, 3571, 542), (550, 3565, 550), (556, 3571, 539), (560, 3564, 560), (564, 3648, 432), (566, 3558, 566), (582, 3552, 582), (584, 3557, 581), (586, 3551, 584), (593, 3551, 582), (598, 3545, 598), (611, 3544, 602), (614, 3539, 614), (630, 3534, 630), (646, 3529, 646)]

===================

Mk14: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 89.8s

[(694, 5085, 694), (699, 5084, 694), (707, 5078, 707), (720, 5072, 720), (733, 5066, 733), (746, 5060, 746), (759, 5054, 759), (772, 5048, 772), (785, 5042, 785), (798, 5036, 798), (811, 5030, 811), (836, 5028, 836), (861, 5026, 861), (886, 5024, 886), (911, 5022, 911), (936, 5020, 936), (961, 5018, 961), (986, 5016, 986), (1011, 5014, 1011), (1036, 5012, 1036), (1061, 5010, 1061), (1086, 5008, 1086), (1111, 5006, 1111)]

===================

Mk15: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 91.7s

[(396, 4473, 379), (397, 4469, 387), (399, 4463, 391), (401, 4484, 377), (401, 4469, 386), (403, 4472, 379), (404, 4464, 377), (405, 4458, 386), (406, 4458, 379), (410, 4465, 376), (412, 4456, 391), (412, 4447, 399), (413, 4518, 363), (413, 4449, 391), (414, 4451, 387), (415, 4445, 399), (416, 4516, 363), (416, 4436, 401), (418, 4446, 387), (418, 4462, 377), (418, 4497, 367), (419, 4457, 379), (419, 4509, 363), (420, 4489, 375), (421, 4454, 385), (422, 4430, 401), (423, 4453, 379), (423, 4441, 399), (423, 4457, 377), (424, 4452, 379), (425, 4478, 375), (428, 4491, 365), (428, 4445, 391), (428, 4439, 399), (429, 4442, 387), (429, 4436, 391), (430, 4428, 415), (431, 4475, 375), (432, 4424, 413), (432, 4428, 411), (434, 4426, 407), (435, 4418, 415), (436, 4506, 363), (438, 4407, 429), (438, 4414, 423), (440, 4417, 415), (441, 4403, 430), (441, 4530, 356), (442, 4413, 424), (443, 4432, 397), (444, 4423, 410), (444, 4399, 442), (446, 4485, 365), (449, 4420, 413), (450, 4397, 441), (450, 4448, 386), (451, 4402, 439), (451, 4497, 362), (452, 4452, 377), (452, 4412, 423), (453, 4479, 367), (453, 4405, 429), (453, 4388, 453), (454, 4448, 381), (455, 4395, 448), (455, 4398, 437), (456, 4382, 453), (459, 4392, 437), (459, 4378, 453), (460, 4410, 427), (461, 4456, 376), (462, 4385, 443), (464, 4389, 442), (465, 4370, 465), (465, 4399, 434), (466, 4375, 455), (466, 4415, 419), (466, 4408, 427), (467, 4383, 448), (467, 4503, 360), (468, 4368, 467), (471, 4428, 404), (476, 4402, 432), (476, 4363, 468), (476, 4364, 467), (476, 4380, 451), (479, 4405, 427), (479, 4357, 479), (480, 4359, 473), (482, 4356, 479), (483, 4350, 481), (484, 4354, 479), (484, 4374, 455), (485, 4351, 479), (486, 4403, 429), (486, 4401, 432), (487, 4373, 461), (489, 4414, 419), (489, 4371, 460), (489, 4409, 423), (490, 4349, 482), (491, 4365, 465), (491, 4350, 479), (492, 4362, 471), (493, 4345, 493), (493, 4406, 425), (494, 4373, 458), (495, 4342, 495), (496, 4341, 493), (498, 4379, 451), (499, 4340, 493), (500, 4338, 498), (501, 4396, 432), (502, 4347, 492), (504, 4346, 491), (505, 4384, 446), (506, 4333, 504), (506, 4339, 493), (507, 4331, 507), (507, 4337, 496), (509, 4330, 509), (509, 4334, 503), (510, 4414, 418), (511, 4347, 484), (512, 4328, 511), (513, 4328, 507), (514, 4327, 507), (515, 4326, 515), (516, 4324, 515), (518, 4377, 451), (518, 4358, 473), (519, 4323, 519), (521, 4317, 521), (521, 4336, 498), (521, 4323, 516), (523, 4315, 523), (524, 4390, 439), (525, 4316, 521), (525, 4314, 523), (527, 4322, 517), (528, 4313, 528), (529, 4312, 527), (531, 4311, 530), (532, 4311, 529), (533, 4315, 521), (535, 4307, 535), (537, 4304, 537), (537, 4345, 492), (537, 4310, 532), (540, 4309, 533), (541, 4303, 541), (542, 4300, 541), (544, 4373, 455), (545, 4303, 540), (547, 4311, 528), (547, 4310, 530), (548, 4298, 548), (548, 4299, 543), (549, 4302, 540), (551, 4293, 551), (551, 4304, 535), (553, 4291, 553), (554, 4288, 554), (555, 4290, 553), (558, 4612, 355), (559, 4289, 553), (561, 4291, 551), (564, 4287, 557), (566, 4284, 566), (567, 4278, 567), (567, 4286, 565), (571, 4297, 548), (573, 4276, 573), (574, 4287, 556), (578, 4303, 537), (578, 4298, 544), (579, 4272, 579), (583, 4274, 578), (583, 4267, 583), (593, 4263, 591), (597, 4273, 578), (599, 4258, 599), (603, 4261, 598), (606, 4256, 599), (615, 4251, 615), (630, 4249, 623), (631, 4244, 631)]

Challenges

Mk10 stands out. The best single-objective result we found in the literature has makespan < 200. The best published solution we found with a Gantt diagram has makespan=213, see Hao

FJSP

Our multi-objective solution

Mk10: modecpp.retry with retry_num=32, popsize = 48, max_eval = 960000, workers=16, time = 83.0s

[(236, 1899, 218), (237, 1896, 215), (237, 1894, 220), (239, 1893, 215), (239, 1891, 220), (240, 1886, 218), (241, 1881, 220), (242, 1878, 220), (243, 1900, 214), (243, 1901, 210), (244, 1898, 212), (244, 1891, 215), (244, 1876, 225), (245, 1874, 225), (245, 1888, 215), (246, 1882, 215), (246, 1875, 218), (247, 1873, 235), (247, 1908, 209), (248, 1871, 230), (248, 1870, 240), (248, 1874, 220), (248, 1887, 212), (248, 1872, 221), (249, 1881, 216), (249, 1872, 220), (250, 1869, 225), (251, 1879, 215), (251, 1893, 210), (251, 1869, 220), (252, 1877, 216), (252, 1864, 227), (252, 1891, 210), (253, 1899, 209), (254, 1889, 210), (254, 1897, 209), (254, 1863, 235), (254, 1886, 212), (255, 1883, 212), (255, 1877, 215), (255, 1866, 225), (255, 1862, 245), (256, 1904, 208), (256, 1860, 240), (256, 1861, 230), (257, 1895, 209), (257, 1887, 211), (257, 1857, 250), (260, 1859, 236), (261, 1863, 227), (262, 1858, 249), (262, 1856, 260), (262, 1860, 235), (262, 1866, 224), (262, 1863, 225), (263, 1858, 240), (265, 1861, 227), (265, 1857, 240), (265, 1858, 230), (266, 1854, 250), (266, 1856, 236), (267, 1855, 240), (272, 1852, 270), (273, 1858, 228), (273, 1857, 235), (276, 1853, 260), (276, 1855, 230), (276, 1854, 240), (278, 1851, 250), (282, 1903, 208), (283, 1853, 236), (283, 1852, 240), (284, 1850, 260), (284, 1849, 270), (289, 1848, 280), (321, 1847, 290)]

was already significantly better than

Mk10: Results_TSM.txt from https://moda.liacs.nl/code/KefalasEtAl2019-Supplement.zip

[(300, 2157, 224),  (311, 2128, 256),  (313, 2190, 220),  (313, 2127, 242),  (313, 2132, 241),  (314, 2133, 230),  (315, 2156, 220),  (316, 2128, 220),  (317, 2127, 211),  (318, 2113, 239),  (318, 2125, 230),  (321, 2101, 259),  (322, 2122, 223),  (323, 2113, 224),  (324, 2112, 217),  (325, 2094, 220),  (326, 2090, 221),  (331, 2109, 214),  (332, 2171, 210),  (333, 2137, 210),  (335, 2106, 218),  (336, 2087, 233),  (336, 2112, 208),  (339, 2082, 229),  (343, 2109, 213),  (345, 2107, 216),  (353, 2105, 215),  (357, 2082, 220),  (358, 2111, 212),  (359, 2069, 253),  (359, 2091, 208),  (362, 2080, 250),  (362, 2081, 236),  (363, 2057, 242),  (364, 2054, 210),  (364, 2128, 205),  (368, 2115, 206),  (390, 2092, 205),  (397, 2050, 248),  (416, 2084, 206),  (427, 2127, 204),  (452, 2082, 206),  (460, 2078, 209),  (515, 2132, 202)]

What happens if we invest much more time and adapt the optimization parameters? Using three objectives, we find the following Pareto front, which contains a makespan=216 solution:

The optimization needed 34644 seconds and 5366235220 function evaluations.

Mk10: modecpp.retry with retry_num=640, popsize = 500, max_eval = 16000000, workers=16), time = 34644s

[(216.0, 1934.0, 212.0), (217.0, 1923.0, 210.0), (217.0, 1937.0, 207.0), (217.0, 1933.0, 208.0), (217.0, 1944.0, 203.0), (217.0, 1952.0, 201.0), (217.0, 1941.0, 205.0), (217.0, 1947.0, 202.0), (218.0, 1936.0, 205.0), (218.0, 1989.0, 200.0), (218.0, 1918.0, 212.0), (218.0, 1921.0, 210.0), (218.0, 1939.0, 203.0), (218.0, 1924.0, 207.0), (218.0, 1949.0, 201.0), (218.0, 1944.0, 202.0), (219.0, 1921.0, 208.0), (219.0, 1918.0, 210.0), (219.0, 1913.0, 212.0), (220.0, 1936.0, 203.0), (220.0, 1915.0, 210.0), (220.0, 1971.0, 200.0), (220.0, 1933.0, 205.0), (221.0, 1956.0, 200.0), (221.0, 1963.0, 196.0), (221.0, 1941.0, 202.0), (221.0, 1930.0, 205.0), (221.0, 1977.0, 195.0), (221.0, 1905.0, 221.0), (221.0, 1910.0, 217.0), (221.0, 1911.0, 214.0), (222.0, 1928.0, 205.0), (222.0, 1920.0, 207.0), (222.0, 1934.0, 204.0), (222.0, 1908.0, 214.0), (222.0, 1912.0, 210.0), (222.0, 1946.0, 201.0), (222.0, 1898.0, 216.0), (222.0, 1953.0, 200.0), (222.0, 1905.0, 215.0), (222.0, 1974.0, 195.0), (222.0, 1962.0, 197.0), (222.0, 1910.0, 212.0), (223.0, 1960.0, 198.0), (223.0, 1914.0, 209.0), (223.0, 1945.0, 200.0), (223.0, 1919.0, 207.0), (223.0, 1917.0, 208.0), (223.0, 1905.0, 213.0), (223.0, 1934.0, 203.0), (223.0, 1931.0, 204.0), (223.0, 1926.0, 205.0), (223.0, 1901.0, 215.0), (223.0, 1910.0, 210.0), (223.0, 1907.0, 212.0), (224.0, 1916.0, 207.0), (224.0, 1897.0, 216.0), (224.0, 1935.0, 201.0), (224.0, 1931.0, 203.0), (224.0, 1925.0, 205.0), (224.0, 1933.0, 202.0), (224.0, 1915.0, 208.0), (224.0, 1906.0, 210.0), (224.0, 1898.0, 215.0), (224.0, 1901.0, 213.0), (224.0, 1910.0, 209.0), (224.0, 1903.0, 212.0), (224.0, 1896.0, 219.0), (225.0, 1929.0, 204.0), (225.0, 1959.0, 199.0), (225.0, 1988.0, 194.0), (225.0, 1897.0, 215.0), (225.0, 1899.0, 212.0), (225.0, 1919.0, 205.0), (225.0, 1894.0, 216.0), (225.0, 1904.0, 210.0), (226.0, 1929.0, 203.0), (226.0, 1902.0, 210.0), (226.0, 1908.0, 209.0), (226.0, 1891.0, 217.0), (226.0, 1913.0, 208.0), (227.0, 1889.0, 220.0), (227.0, 1926.0, 204.0), (227.0, 1957.0, 196.0), (227.0, 1893.0, 216.0), (227.0, 1912.0, 208.0), (227.0, 1895.0, 215.0), (227.0, 1897.0, 212.0), (227.0, 1900.0, 210.0), (227.0, 1915.0, 205.0), (227.0, 1952.0, 197.0), (227.0, 1936.0, 200.0), (227.0, 1947.0, 199.0), (227.0, 1934.0, 201.0), (228.0, 1895.0, 214.0), (228.0, 1965.0, 195.0), (228.0, 1979.0, 194.0), (228.0, 1896.0, 212.0), (228.0, 1883.0, 220.0), (228.0, 1892.0, 215.0), (228.0, 1889.0, 216.0), (228.0, 1886.0, 217.0), (228.0, 1914.0, 206.0), (228.0, 1934.0, 200.0), (228.0, 1927.0, 201.0), (228.0, 1924.0, 204.0), (228.0, 1903.0, 209.0), (228.0, 1899.0, 210.0), (229.0, 1962.0, 195.0), (229.0, 1893.0, 212.0), (229.0, 1910.0, 208.0), (229.0, 1882.0, 220.0), (229.0, 1898.0, 211.0), (229.0, 1956.0, 196.0), (229.0, 1889.0, 215.0), (229.0, 1923.0, 204.0), (229.0, 1888.0, 216.0), (229.0, 1885.0, 217.0), (229.0, 1926.0, 203.0), (230.0, 1879.0, 220.0), (230.0, 1892.0, 212.0), (230.0, 1909.0, 208.0), (230.0, 1895.0, 210.0), (230.0, 1878.0, 230.0), (230.0, 1951.0, 198.0), (230.0, 1901.0, 209.0), (230.0, 1885.0, 215.0), (231.0, 1900.0, 209.0), (231.0, 1882.0, 218.0), (231.0, 1884.0, 217.0), (231.0, 1907.0, 208.0), (231.0, 1887.0, 212.0), (231.0, 1894.0, 210.0), (231.0, 1911.0, 207.0), (231.0, 1913.0, 205.0), (231.0, 1920.0, 204.0), (231.0, 1949.0, 198.0), (232.0, 1946.0, 199.0), (232.0, 1910.0, 206.0), (232.0, 1977.0, 194.0), (232.0, 1883.0, 215.0), (232.0, 1878.0, 225.0), (232.0, 1892.0, 211.0), (232.0, 1882.0, 216.0), (233.0, 1912.0, 205.0), (233.0, 1873.0, 225.0), (233.0, 1885.0, 214.0), (233.0, 1891.0, 210.0), (233.0, 1897.0, 209.0), (233.0, 1906.0, 208.0), (233.0, 1877.0, 224.0), (233.0, 1878.0, 220.0), (233.0, 1933.0, 200.0), (233.0, 1879.0, 215.0), (233.0, 1939.0, 199.0), (233.0, 1941.0, 198.0), (233.0, 1924.0, 203.0), (234.0, 1875.0, 218.0), (234.0, 1872.0, 220.0), (234.0, 1938.0, 199.0), (234.0, 1870.0, 227.0), (234.0, 1877.0, 216.0), (234.0, 1869.0, 230.0), (234.0, 1911.0, 205.0), (235.0, 1929.0, 200.0), (235.0, 1988.0, 191.0), (235.0, 1918.0, 204.0), (235.0, 1926.0, 201.0), (235.0, 1952.0, 196.0), (235.0, 1976.0, 194.0), (235.0, 1923.0, 203.0), (235.0, 1909.0, 207.0), (235.0, 1944.0, 197.0), (236.0, 1870.0, 225.0), (236.0, 1915.0, 204.0), (236.0, 1908.0, 205.0), (237.0, 1905.0, 208.0), (237.0, 1864.0, 227.0), (237.0, 1869.0, 225.0), (237.0, 1951.0, 196.0), (238.0, 1868.0, 225.0), (238.0, 1863.0, 235.0), (238.0, 1914.0, 204.0), (238.0, 1973.0, 194.0), (238.0, 1885.0, 212.0), (238.0, 1869.0, 220.0), (238.0, 1979.0, 191.0), (239.0, 1866.0, 226.0), (239.0, 1960.0, 195.0), (239.0, 1903.0, 208.0), (239.0, 1890.0, 211.0), (239.0, 1907.0, 205.0), (240.0, 1866.0, 225.0), (240.0, 1974.0, 191.0), (240.0, 1889.0, 210.0), (240.0, 1994.0, 190.0), (240.0, 1972.0, 194.0), (241.0, 1902.0, 208.0), (241.0, 1895.0, 209.0), (242.0, 1877.0, 215.0), (242.0, 1883.0, 212.0), (242.0, 1887.0, 211.0), (242.0, 1861.0, 230.0), (243.0, 1860.0, 240.0), (243.0, 1955.0, 195.0), (244.0, 1906.0, 207.0), (245.0, 2010.0, 189.0), (247.0, 1993.0, 190.0), (247.0, 1858.0, 240.0), (247.0, 1859.0, 236.0), (248.0, 1861.0, 227.0), (248.0, 1860.0, 235.0), (248.0, 1868.0, 224.0), (248.0, 1865.0, 225.0), (249.0, 1866.0, 224.0), (249.0, 1901.0, 208.0), (249.0, 1863.0, 225.0), (250.0, 1855.0, 240.0), (250.0, 1973.0, 193.0), (250.0, 1856.0, 236.0), (251.0, 1858.0, 230.0), (252.0, 1854.0, 250.0), (253.0, 1970.0, 191.0), (253.0, 1967.0, 192.0), (255.0, 2001.0, 189.0), (255.0, 1966.0, 194.0), (256.0, 1900.0, 208.0), (259.0, 1860.0, 228.0), (260.0, 1853.0, 260.0), (260.0, 1857.0, 235.0), (260.0, 1858.0, 228.0), (261.0, 1854.0, 245.0), (262.0, 1855.0, 230.0), (262.0, 1852.0, 240.0), (262.0, 1853.0, 236.0), (263.0, 1851.0, 250.0), (264.0, 1850.0, 260.0), (267.0, 1990.0, 190.0), (270.0, 1849.0, 270.0), (272.0, 1925.0, 202.0), (273.0, 1997.0, 189.0), (280.0, 1848.0, 280.0), (290.0, 1847.0, 290.0)]

Eliminating the last objective simplifies the task significantly. In that setting we find a makespan = 208 solution, which is not far from the best solution ever found using single-objective optimization.

The optimization needed 3669 seconds and 1207225466 function evaluations.

Mk10: modecpp.retry with retry_num=640, popsize = 480, max_eval = 16000000, workers=16), time = 3669s

[(208.0, 1978.0), (209.0, 1973.0), (210.0, 1967.0), (211.0, 1966.0), (212.0, 1959.0), (213.0, 1955.0), (214.0, 1941.0), (215.0, 1928.0), (216.0, 1926.0), (217.0, 1923.0), (218.0, 1917.0), (219.0, 1913.0), (220.0, 1910.0), (221.0, 1903.0), (222.0, 1900.0), (223.0, 1896.0), (224.0, 1895.0), (225.0, 1894.0), (226.0, 1882.0), (229.0, 1881.0), (230.0, 1875.0), (231.0, 1874.0), (233.0, 1869.0), (234.0, 1866.0), (237.0, 1864.0), (239.0, 1863.0), (241.0, 1861.0), (242.0, 1858.0), (248.0, 1855.0), (250.0, 1854.0), (259.0, 1853.0), (260.0, 1850.0), (270.0, 1849.0), (280.0, 1848.0), (290.0, 1847.0)]

Alternatively, we get a makespan = 210 solution with a better second objective:

The optimization needed 605 seconds and 194758803 function evaluations.

Mk10: modecpp.retry with retry_num=640, popsize = 480, max_eval = 16000000, workers=16), time = 605s

(210.0, 1944.0), (212.0, 1933.0), (214.0, 1930.0), (215.0, 1924.0), (216.0, 1921.0), (217.0, 1913.0), (219.0, 1911.0), (220.0, 1907.0), (221.0, 1899.0), (222.0, 1896.0), (225.0, 1892.0), (226.0, 1888.0), (227.0, 1886.0), (228.0, 1882.0), (229.0, 1878.0), (233.0, 1875.0), (234.0, 1873.0), (235.0, 1868.0), (237.0, 1866.0), (240.0, 1864.0), (243.0, 1860.0), (244.0, 1858.0), (247.0, 1857.0), (250.0, 1854.0), (252.0, 1853.0), (255.0, 1851.0), (260.0, 1850.0), (270.0, 1849.0), (280.0, 1848.0), (290.0, 1847.0)]

This time we used a custom termination check is_terminate(ys, workers, max_evals). Its purpose is to stop a modecpp optimization run early if the intermediate result is below average and is unlikely to affect the final overall result much. We configure three checkpoints:

self.checks = [int(max_evals/33), int(max_evals/10), int(max_evals/3.3)]

ys = mp.RawArray(ct.c_double, workers) is shared between workers and records their current progress. self.limits[i] = np.sort(np.array(int(yi) for yi in self.ys[:]])) takes a snapshot when a checkpoint is reached for the first time. This snapshot defines the threshold for the termination check. We use the 9th, 5th, and 3rd best values as thresholds for the first, second, and third checkpoint. A snapshot is necessary because progress keeps improving as the run continues, so the thresholds would otherwise become harder to reach over time. modecpp.retry calls is_terminate.reinit before each parallel optimization, so we can reinitialize the thread-local variables. All variables except ys are thread local. We create only one instance of is_terminate, but Python multiprocessing creates 16 more, one for each worker process created by modecpp.retry. is_terminate keeps all information needed for its termination decision from the function values y it receives through call(self, x, y).

class is_terminate(object):

    def __init__(self, ys, workers, max_evals):
        self.count = 0
        self.score = 1E99
        self.terminate = False
        self.ys = ys
        self.workers = workers
        self.max_evals = max_evals
        self.limits = [None,None,None]
        self.checks = [int(max_evals/33), int(max_evals/10), int(max_evals/3.3)]
        self.ci = [8, 4, 2]

    def reinit(self):
        self.count = 0
        self.score = 1E99
        self.terminate = False

    def __call__(self, x, y):
        self.count += 1
        pid = os.getpid() % self.workers
        if y[0] < self.ys[pid]:
            self.ys[pid] = y[0]
        if y[0] < self.score:
            self.score = y[0]
        for i in range(len(self.limits)):
            if self.count == self.checks[i]:
                if self.limits[i] is None:
                    self.limits[i] = np.sort(np.array([int(yi) for yi in self.ys[:]]))
                if self.score >= self.limits[i][self.ci[i]]:
                    self.terminate = True
        return self.terminate

    ...
    workers = 16
    max_evals = 16000000
    ys = mp.RawArray(ct.c_double, workers)
    for i in range(workers): ys[i] = 1E99
    xs, front = modecpp.retry(fit.fun, fit.nobj, fit.ncon, fit.bounds, num_retries=6400, popsize = 480,
              max_evaluations = max_evals, nsga_update = True, logger = logger(),
              is_terminate = is_terminate(ys, workers, max_evals),
              workers=workers)

Asteroid harvesting

For Mk10 asteroid harvesting with 5 factories, single-objective optimization gives makespan = 484:

The optimization needed 21916 seconds and 2865206239 function evaluations. BiteOpt was called using

    retry.retry(store, Bite_cpp(1960000,M=1).minimize, num_retries=1600)

It would be interesting to see whether other methods can improve these results.