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 subconsiously 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 being on time.

Scheduling was something that I was a fan of, the goal of their science is to find the perfect sequence of tasks that meets a set of requirements. Their motives may sound simple but the average scheduling puzzles are \(NP-hard\), our current understanding on combinatorics encourages the development of heuristical approaches to tackle the 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 manouvers 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 fullfill 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: \(P \,||\, \text{prec} \,,M_{j}||\, C_{\text{max}}\).

Small disclaimer:

The machines setup

Most of the parallel machine and single machine problems, are positioned in the NP- and P complete spectrum. Precedence constraints are essential because you can't mix veggies before cutting them. the aim is to minimize the global completion time or else I would miss the train. There would be no heuristics here to speak of, just a direct method, specifically a list scheduling algorithm since it has been proven by Shutten(2003) that parallel machine problems with setup times or precedence constraints can be solved to optimality with the aformentioned algorithm, Except it's not a list here that we are talking about but a graph of sorts: I will be traversing the graph and checking for dependencies as I keep moving forward until I hit the last node.
As for the constraints here is how I dealt with some of these:

• 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 seperate 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.
As for 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 omelette sandwish.

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 an 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 imeplement 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.

References

J.M.J. Schutten, List scheduling revisited, Operations Research Letters, Volume 18, Issue 4, 1996, Pages 167-170, ISSN 0167-6377, https://doi.org/10.1016/0167-6377(95)00057-7