Solving printing press job sequencing problem with a new heuristic algorithm

Abstract

Job sequencing problems can be found widely in the industrial sector. Applications of operation research are used to find optimal solutions to these problems. Since the number of jobs and machines is large in practical situations, developing a job sequence in industry is difficult. Since job sequencing is a dynamic process, a job pool depends on time. So it has to be updated every day. Earliest Due Date (EDD) with the machine completion time has to be considered to minimize the tardiness. In this article, scheduling is considered relating to the printing industry. In general, customers’ requirements should be satisfied while maximizing the overall profit of the printing press. Here the objective is to develop a general heuristic algorithm to obtain an optimum job sequence of n jobs on m machines based on EDD and greedy approach by minimizing the total idle time of the machines. Generally, machines can run up to that specific level, and their maximum expected production can be accomplished. The proposed algorithm achieves the maximum machine capacity by selecting the job, which has the minimum machine idle time. So the production can be maximized and the machine failures can be minimized. Hence, the optimum sequence obtained by this proposed algorithm helps to maximize the profit of the printing press indirectly. The operation of the proposed algorithm was illustrated by a numerical example with the use of Microsoft Excel. The input parameters are the order placing date, due date of the jobs and processing time for every job in the supplied machines. The proposed algorithm is comparable to the developed Branch and Bound algorithm which minimizes the tardiness and total completion time separately. This heuristic algorithm combines both objectives together and along with the addition of dynamic approach. The interruption of the currently processing jobs can be minimized by handling the process according to optimum job sequence. However, the current due date of any job which cannot be completed on or before the due date can be postponed if the customer agrees to it, and can be included in the process.