Notation

Intro

As a guy who is very passionate about combinatorial optimization, and as much as I kept editing the core of my website's layout, I thought about adding some spiciness to my articles, even if it defies my minimalistic philosophies.

Living here in Germany slowly and subconsciously turned me into a time-slave. Evil marketers did a really good job at putting emphasis on time, creating a need for goods and services that make me priorities rhythm before myself.

Scheduling was something that I was a fan of, the goal of their science is to come up with strategies and solution methods to solve scheduling problems. Their motives may sound simple but the average scheduling puzzles are \(NP-hard\), our current understanding on combinatorics encourages the development of heuristic approaches to tackle the hardships of investigating permutations by offering a solution that is good enough.

Cooking just began to slowly become an integral part of my life, my life style makes it hard for me to innovate, I just keep cycling through a limited set of recipes. Old habits die hard, at least they do. When I feel energetic, my dexterity goes top notch, enabling fast reactions and quick maneuvers across the kitchen, but sometimes I just brute force my structures without thinking, which can result in a chunk of wasted time, and sometimes effort.

In the theory of scheduling, if a given situation is properly formulated, you may gain access to tools that aid you reach your goals, without having to rely on any form of soft experience. This can be achieved by understanding the setup and trying to perceive it with intelligence, after all, the methods of logistics aim to exploit all kinds of information in order to fulfill an objective. I thought a lot about how to design a nice scheduling setup for a cooking context, not chaining tasks as quick as possible may cause your food to catch a cold.

After tinkering with lots of tools, I thought about simplifying the scheduling formulation in a way that reduces the amount of constraints that I have to account for. What I will be proposing is the work of an amateur, as of yet:

Small disclaimer:

The machines setup

This setup assumes the following characteristics:

• The sequencing of each task is known, the task assignment for each machine is known, what is unknown however is the makespan
• Preemption: Instead of stopping the machine and resuming afterwards, I made it so that it is treated as \(n\) number of phases, each of which will describe their states.
• Setup times: These will either be modeled as a separate task similarly to the previous constraint, or in some occasions I might just combine everything together as a single task.

• Bauknecht oven with 2 slots
• Panasonic NN E221MM
• Schott Seran stove set
• Unnamed toast machine
• Me and my tools

The formulation:

Before talking about the design let me define what a machine is. Pretty much anything that processes a task on its own without any active moderation from my end. My kitchen is equipped with a stove, an oven, and microwave- all of which can act on their own provided I initiate them - As for me, I have my own hands which will act as a medium to craft the best of the best. Specs-wise, I think the machines and I are modern enough.
Concerning the precedence graph, I will not go into deep details on the chain of tasks unless it is necessary. The quantity of my descriptions should, in theory, not influence the makespan; micro tasks like "breaking an egg and then mixing it up" will be summed up as "preparing the egg" for the sake of simplicity.

Example:

Here I will be showcasing a small example of how to model the Gantt chart of preparing an omelet sandwich.

Tasks:

1. Prepare the egg
2. Cut the veggies
3. Cook the egg
4. Prepare the bread
5. Stuff in the bread

Machines/Tasks set:

• Me = {1,2,4,5}
• Stove = {3}

And these can be modeled like so, because you can't stuff anything in the bread as long as your eggs aren't ready:

I will not attribute any processing times in this example, just picture any arbitrary number for each task for now.

About the computation

            {{ $tasks := .Params.tasks }}
                var processSteps = [
  {{- range $index, $task := $tasks -}}
    {
      id: {{ $task.id }},
      name: "{{ $task.name }}",
      machine: "{{ $task.machine }}",
      processing_time: {{ $task.processing_time }},
      dependencies: [{{ range $task.dependencies }}{{ . }},{{ end }}],
    },
  {{- end -}}
];

function calculateSchedule(processSteps) {
    const tasks = processSteps.map((step, index) => ({
        id: index + 1,
        name: step.name,
        machine: step.machine,
        processingTime: step.processing_time,
        dependencies: step.dependencies,
        startTime: 0,
        finishTime: 0,
        lst: 0,
    }));

    for (const task of tasks) {
        task.startTime = Math.max(...task.dependencies.map(depId => tasks[depId - 1].finishTime), 0);
        task.finishTime = task.startTime + task.processingTime;
    }

    for (const task of tasks) {
        const successors = tasks.filter(t => t.dependencies.includes(task.id));
        const lstCandidates = successors.map(s => s.startTime - task.processingTime);
        task.lst = Math.max(...lstCandidates, 0);
    }

    const makespan = Math.max(...tasks.map(task => task.finishTime));

    return { makespan, tasks };
}

const scheduleResult = calculateSchedule(processSteps);
console.log('Makespan:', scheduleResult.makespan);
console.log('Task Schedule:');
scheduleResult.tasks.forEach(task => {
    console.log(`${task.name}: Start Time ${task.startTime}, Finish Time ${task.finishTime}, Machine ${task.machine}`);
});

Can a better formulation beat my makespan ?

I would like to see that! Everything that you have read so far was the effort of two days and is subject for potential improvements. For now I am happy with the results, though if I get any new ideas, I will surely implement provide updates. Feel free to submit an issue on the website's repo or send me an email and I will be content to have a discussion on the matter.