Scheduling sequence-dependent colour printing jobs
Date
2016
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Southern African Institute for Industrial Engineering
Abstract
ENGLISH ABSTRACT: A scheduling problem in the colour printing industry is considered in this paper. The problem is to find an optimal assignment of print jobs to each of a set of colour printers, as well as an optimal processing sequence for the set of jobs assigned to each printer. The objective is to minimise the makespan of the schedule to achieve a suitable balance between the workloads of the printers and the efficiencies of the job sequences assigned to the printers. A novel aspect of the problem is the way in which the printer set-up times associated with the jobs are job sequence-dependent — it is possible to exploit commonalities between the colours required for successive jobs on each machine. We solve this problem approximately by using a simple heuristic and three well-known metaheuristics. Besides colour printing, the scheduling problem considered here admits many other applications. Some of these alternative applications are also briefly described.
AFRIKAANSE OPSOMMING: ’n Skeduleringsprobleem uit die kleurdrukwerkbedryf word in hierdie artikel oorweeg. Die probleem vra vir ’n optimale toewysing van take aan elk van ’n versameling kleurdrukkers, sowel as die spesifikasie van ’n optimale volgorde waarin die take wat aan elke drukker toegewys is, uitgevoer moet word. Die doel is om die prosestyd van die drukker wat laaste klaarmaak te minimeer om sodoende ’n aanvaarbare balans tussen die werkladings van die drukkers en die taakvolgorde vir elke drukker te bewerkstellig. ’n Nuwe aspek van die probleem is die manier waarop die opsteltye van die drukkers vir die take volgorde-afhanklik is — dit is moontlik om gemeenskaplikhede tussen die kleure wat vir opeenvolgende take op elke masjien benodig word, uit te buit. Ons los hierdie probleem benaderd op deur gebruik te maak van ’n eenvoudige heuristiek asook drie bekende metaheuristieke. Behalwe vir kleurdrukwerk, het die skeduleringsprobleem wat hier beskou word vele ander toepassings. Sommige van hierdie toepassings word ook kortliks beskryf.
AFRIKAANSE OPSOMMING: ’n Skeduleringsprobleem uit die kleurdrukwerkbedryf word in hierdie artikel oorweeg. Die probleem vra vir ’n optimale toewysing van take aan elk van ’n versameling kleurdrukkers, sowel as die spesifikasie van ’n optimale volgorde waarin die take wat aan elke drukker toegewys is, uitgevoer moet word. Die doel is om die prosestyd van die drukker wat laaste klaarmaak te minimeer om sodoende ’n aanvaarbare balans tussen die werkladings van die drukkers en die taakvolgorde vir elke drukker te bewerkstellig. ’n Nuwe aspek van die probleem is die manier waarop die opsteltye van die drukkers vir die take volgorde-afhanklik is — dit is moontlik om gemeenskaplikhede tussen die kleure wat vir opeenvolgende take op elke masjien benodig word, uit te buit. Ons los hierdie probleem benaderd op deur gebruik te maak van ’n eenvoudige heuristiek asook drie bekende metaheuristieke. Behalwe vir kleurdrukwerk, het die skeduleringsprobleem wat hier beskou word vele ander toepassings. Sommige van hierdie toepassings word ook kortliks beskryf.
Description
CITATION: Schuurman, J. & Van Vuuren, J. H. 2016. Scheduling sequence-dependent colour printing jobs. South African Journal of Industrial Engineering, 27(2):43-59, doi:10.7166/27-2-1119.
The original publication is available at http://sajie.journals.ac.za/pub
The original publication is available at http://sajie.journals.ac.za/pub
Keywords
Production scheduling, Printing industry, Production control, Job-shop scheduling
Citation
Schuurman, J. & Van Vuuren, J. H. 2016. Scheduling sequence-dependent colour printing jobs. South African Journal of Industrial Engineering, 27(2):43-59, doi:10.7166/27-2-1119