The value of time spent for sequencing of jobs in random sized batches

Abstract

In this study, we address the question 'Is it worth scheduling?' by investigating the trade-o between the time spent to obtain the optimal schedule and improvement of the system performance. We consider two queuing systems with batch arrival of jobs. Investigated queuing systems are M=G=1 and M=G=1 systems where batches contain a random number of jobs, the arrival of batches follows a Poisson process and processing time of jobs are arbitrarily distributed. In both systems, servers are able to process one job at a time. In the M=G=1 system, jobs arriving in same batch have to be processed by the same server (batch dedicated server assumption). In these queuing systems, sequencing jobs in arriving batches separately with a static rule is a proxy of optimizing the system and there is a non-negligible time associated with sequencing jobs. In both systems, appropriate functions of ow time of jobs are considered as performance measures. Moreover, a decision rule is proposed to decide whether or not to sequence jobs in an arriving batch where each arriving batch is treated separately. The decision rule is based on the number of jobs in arriving batches because sequencing time of a batch is assumed to be dependent on the number of jobs in it. The general processing policy obtained by applying mentioned decision rule and various policies which are the special cases of the general policy are also discussed. Formulations for performance measures of both systems are derived under various processing policies and their Laplace transforms are also derived for the basic policies where all of the arriving batches are processed according to the same rule. In the numerical study performed for single and in nite server systems, under some simplifying assumptions, the optimal processing policies are determined under various system conditions.