Open-Problem

Symptom You are handed a scheduling problem. Two hundred tasks, precedence constraints, shared resources, and a deadline. Somebody wants an optimal schedule. Checking a proposed schedule takes seconds: walk the list, verify each constraint, add up the makespan. Finding one is different. Your search runs for a day and finds nothing. You try simulated annealing, then a genetic algorithm, then branch and bound. Each gives good schedules and none gives the best one, and you cannot tell whether the problem is hard or you are not clever enough. ...