A Job Sequence Optimization Approach for Parallel Machine Scheduling Problem in Printing Manufacturing Systems

Abstract

This paper investigated a parallel machine scheduling problem in the printing manufacturing systems due to operational requirements on the color-batching of the printed matter and sequential requirements on the sequence adherence of a printing press. Resequencing printing jobs as color-oriented batches reduced the costs of color changes and operational costs for printing shop. Also, post press workshop required printing shops to print jobs with minimal makespan so that high sequence adherence with its demand is assured. Based on real-world applications, we investigated two contradictory objectives-color change costs and minimal makespan-in a parallel high-fidelity printing press scheduling environment. A job sequence optimization approach is proposed. Moving interpolation algorithm and color sequence mapping algorithm are designed to reduce frequency of replacing ink. Base on iterative greedy algorithm, color sequence job groups with the same or similar color sequence are scheduled to the printing presses. Three experiments are conducted and showed that the proposed approach has good feasibility and effectiveness, and convergence in solving minimum completion time. Therefore, the proposed approach can be used in printing shops to improve scheduling efficiency and reduce production costs.

Keywords

• Printing manufacturing systems
• parallel machine scheduling problem
• minimal makespan
• color sequence comparison
• iterated greedy algorithm