The Greedy Algorithm


Share this post

Are Greedy Algorithms creating fabric waste in your business?

The short answer to that question is... probably!

But before we dive into the long answer of reasoning and questioning if our methodology of making cut order plans and markers is resulting in excessive fabric waste and longer than necessary cutting times, we would need to understand what is, a greedy algorithm.

More often than not, we associate the word algorithm with mathematicians, scientists, and computer programmers, but in actual fact, people use algorithms all the time in their daily routines for accomplishing tasks, such as traveling from one place to another, making a sandwich or navigating the shopping isles in the middle of a pandemic, with the minimum contact with other people whilst still getting all your stuff in the minimum amount of time. Did that guy just cough?

Put very simply, algorithms are a set of step-by-step instructions using which, in standard conditions, an input can be converted to the desired output. Like the directions from place A to place B.

What then is a greedy algorithm? A greedy algorithm is a choice you cannot see beyond. It's a clear obvious choice that you have to make given a limited amount of information that exists pretty much, "in the moment". That choice will be followed by other subsequent choices in a “step by step process”. At each step the “user” decides what’s the “best” outcome for that particular stage but not necessary for the complete process.

It's the line that you queue in at immigration because, well, it's the shortest line, isn't it? And shortest means quickest! But wait! The person in front of you has family members in another line and as soon as it looks like you are almost there and you can almost taste the Gin & Tonic waiting for you at your destination, the other family members switch lanes to join the person in front of you, with a cheeky smile and you are now 20 minutes further back!

If only you would have known! If only you would have had more information about the situation, you would have made a different choice!

There is another type of algorithm. It's called an "Optimization algorithm" This requires, data...a LOT of data. To work perfectly it actually needs all the data including all the available options, conditions, constraints and choices you can make starting from where you are now to where you want to be.

Let’s contrast and compare. You are going to climb a mountain!

The data you have is a) the start point coordinates at the base camp (where you are now) and b) the end point coordinates at the top of the mountain (where you want to be)

So what path will you take? There are literally a thousand ways up that mountain but faced with only the information given, you have no choice but to live in the moment and make a full frontal assault and take a direct route up the north face, who knows it might actually be the best way! Are you feeling lucky?

Of course we probably need to define "best" here. Least effort, least time, most fun? most challenging? best view? What my definition of best might not be yours, also, your definition might change depending on the conditions at the time of the assent. Such conditions, low cloud, available time, current fitness etc.

Let's say we are going to choose the quickest most efficient way up the mountain. What information do we need to know in advance to plot that route?

Well, a map would be a good start, an up-to-date map which shows all the possible routes including those less traveled. We need the coordinates and distances, elevations, slope gradients, and type of terrain. The map has been created in the past through the efforts of hundreds of people working together in their separate journeys to measure all aspects of the available paths.

In addition to the map we also need to understand the current weather conditions and our own capabilities and how fast we can travel under those conditions with the equipment we have.

Armed with all the many thousands of possible combinations we can now plot our best route using an optimized algorithm and a lot of data.

Hang on... the top of the mountain is to the North why are you heading off West?

Because I have all the information to get me where I need to be in the best way possible.

I wonder if he knows about that bridge that collapsed last night?

Analogy well and truly in place let’s see how this “greedy” approach is used in apparel manufacturing and specifically when creating a cut-plan.

Like the pathways up the mountain there are literally many hundreds of thousands of possible cut-plans available for each PO. The number of combinations relates mostly to the number of size variations required in the PO. A number that continues to rise as more brands and retailers pivot to incorporate greater choice for their customers through online and omni-channel sales approaches.

That said the reliability of fabric quality in terms of widths, shrinkages and shade also plays a part, as does the control and capabilities in subsequent processes such as bundling, the cutting process itself, and any subsequent production automation which has a “preference” for size batching.

What we need is a map which can put together all the options and constraints to give the best solution.

Like in our analogy what constitutes “best” will depend on a wide range of attributes which may be preferred over other alternatives, and which may be subject to change depending on the stage of the process, for example fabric costing, buying or cutting, as well as available resources at the time and fabric properties which may or may not be as expected. Whether or not any additional fabric can be used to add value in the current or future PO’s will also be a consideration.

In some cases, reducing fabric yield may be preferred, in others, reducing the length and number of markers or cuts may be a priority as may be maximizing the ply height. Maybe the main determining factor of what constitutes “best” is the ability to make and fulfill the PO in batches.

For simplicity let’s say that you do in fact want to prioritize reducing yield above all other factors, it is rarely that simple, but the analogy holds true whatever “best” happens to be. What you now need is a set of markers that, when viewed holistically gives that lowest yield. It is not necessarily the most efficient marker achievable or indeed the one that you judge, based on your experience to be a high-efficiency marker, nor is it the one that maximizes the cut quantity. (You have climbed lots of similar mountains in the past don’t forget)

Every journey up a mountain begins with a single step, and without a map we take that step armed only with (as good as it is) our experience and wit. What’s clear though is that our first steps will determine the future paths which we can take up the mountain.

Back in the cutting room I want to minimize yield, so my first marker will be one that I judge does just that and if possible, for as many sizes as possible.

I think it’s a good start but what I have just done is to remove hundreds of thousands of other possible markers from place 2, 3, 4, 5, etc in my cut-plan, because they don’t fit with the balance quantities which I need to produce. My end result is now subject to the combination of a hundred or so possible markers rather than hundreds of thousands.

Each and every marker I chose as my next sequentially planned marker will reduce the options for the subsequent markers in the plan. Until quite quickly all thoughts are directed solely at making up the remaining quantity balance and not at optimizing yield.

Instead of selecting markers based on whether it's a "good marker" I should have been selecting for good markers which also have the best compatibility with thousands of other good markers which make the correct PO quantities.

This process happens over and over again in many apparel factories on a daily basis where, in the absence of any credible map, talented people make their “best guess” in the shortest possible amount of time available.

Clearly what’s needed then is a “map-making department” consisting of thousands of people creating thousands of markers with known efficiencies and lengths together with all the possible cut-plan combinations for each PO.

Or of course, an automated solution to let one person do the same thing in less time than it currently takes to create a single cut-plan with whatever marker efficiencies happen to be selected.

ShapeShifter is a cloud-based, fabric, & resource hyper-automation solution, tailored to help fashion supply-chains overcome the pain of fabric costing, buying, & cutting by reducing lead-times, effort, & waste.

© Shapeshifter technology group
Privacy Policy
Website by Friday Creative