Machine Scheduling in Printing: a Problem from the Industry with Sequence-Dependent Setup Times and Precedence

Abstract

We have solved the Adaptive Multi-Resource Production Scheduling (AMRPS). Our solution contains a collection of jobs that contain tasks, and days that contain machines that simultaneously contain those tasks. For our current solution, those days are always ten, representing two workweeks. The start and end time of each task is documented and based on their prerequisite task and the other tasks on the machine. We aim to distribute the workload as evenly as possible, although many other factors are in play and therefore this is not always possible. One of the factors that often prevents this is that the jobs should also be finished as closely to their deadline as possible, while still keeping some buffer time into account for handling errors. In practice, this usually means finishing the job one day before it is supposed to be sent out for shipping. We also try to keep some buffer time between tasks within the same job, depending on the size of the order with a larger buffer for a larger order. Another important factor to them is how many times you change the material in a day. One of the printers is based on roll printing and the rolls are difficult to remove from storage and install. This is why additionally the company would prefer to start with the same material they ended with the previous day. Sequence dependent setup times would add additional time, but we also add penalty cost for the material changes because it’s considered a waste of time and resources to do when it is not necessary. Creating this solution as ‘semi-infinite’ was instrumental in making a maximally flexible schedule that can handle frequent underfull-ness. In the future, we may fine-tune so that the length of the schedule stays within reasonable bounds and there is some possibility for jobs to move past their deadline, but some form of semi-infinite days will remain.