CODEWITHSUNDEEP
javaalgorithm
mike
mike

Reputation: 5055

How to find minimal set of operations to meet requirements

I think it's easier, if I show my code first.

/* Machine that can add and remove pools to its stack */
public class Machine {
  private final int toolQuantity = 5;
  public boolean addTool(Tool t)    { return true; }
  public boolean removeTool(Tool t) { return true; }
  public boolean processJob(Job j)  { return true; }
}

/* Tool that is needed to process jobs */
class Tool {
}

/* Job that needs specific tools to be processed on machine */
class Job {
  private final List<Tool> needs = Collections.emptyList();
}

interface Command { public void execute(); }

class AddTool implements Command {
  private Machine m;
  private Tool t;
  @Override
  public void execute() { }
  }

class RemoveTool implements Command {
  private Machine m;
  private Tool t;
  @Override
  public void execute() { }
}

Simplyfied code. Aim was just to communicate the idea

So, I have a machine which processes jobs. Jobs need tools (and the tools have an unlimited lifetime). My aim is to find a minimal list of jobs and commands (i. e. instances of AddTool and RemoveTool so that: {"AddTool(x), "job1", AddTool(y), "job2"}), so that a given fixed list of jobs can be processed. Tools that are not needed by a job, can remain on the machine (as long as there is enough place left of course).

I have two approaches:

Collect requierements from job to job. Since this approach only considers job i and job i + 1. It may not be optimal in cases where machine unloads a tool not needed by job i + 1 but needed by job i + 2. That's an unnecessary cycle of removing and adding (given there was the possibility to remove another not needed tool).

Use an heuristic algorith, e. g. simulated annealing, that minimizes the number of commands used.

I would prefer to use a straight forward aproach. But I can't think of another and I guess the simple approach is too unefficient.

So how can I solve my problem? How can it be classified in terms of computer science? I would also appreciate general solutions to these kind of problems that don't specificly handle jobs, machines and tools.

Upvotes: 2

Views: 152

Answers (1)

kutschkem
kutschkem

Reputation: 8163

This is a hamiltonian path problem, or maybe a Traveling Salesman Problem(if you modify the problem a little bit). Each job needs a certain amount of tools, and you can determine how many commands are needed to get from one job to the other. You want a path through that graph that minimizes the "distance" in terms of additions/removals and visits all nodes/jobs.

Upvotes: 3

Related Questions