Priority scheduling revisited : dominant rules, open protocols and integrated order management

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
School of Business | Doctoral thesis (monograph) | Defence date: 2005-12-09
Checking the digitized thesis and permission for publishing
Instructions for the author
Degree programme
xii, 178, [11] s.
Acta Universitatis oeconomicae Helsingiensis. A, 264
The task of job shop scheduling – determining the sequence and timing of jobs on available resources – is one of the most discussed practical problems in operations management. There are many appropriate problem definitions for job shop scheduling due to the complex and dynamic nature of the problem with a large number of variables and constraints linked to jobs and resources, such as specific due dates, processing times, handling/routing requirements, and capacities not to mention alternative performance measures including maximum and mean tardiness, mean flow time, and portion of tardy jobs. Combinatorially the problems are NP-hard except for a few static one-machine problems with linear objective functions, in which shortest processing time and earliest due date rules are known to give optimal results for mean flow time and maximum tardiness, respectively. This thesis looks into the coordinating power of priority scheduling when customers request different response times and suppliers do their best to fulfill the customer expectations, especially if enforced with differential pricing. The objective of scheduling is assumed to be finding a trade-off between loading efficiency and delivery accuracy when costs include items such as holding costs, tardiness penalties, and expediting charges. From an extensive review of literature on practical applications and studies in index-based scheduling heuristics it appears that no single dominant priority index rule has been suggested for dynamic job shop problems with tardiness-related criteria. Motivated by some conflicting results published on the performance of priority index rules as well as the increasing uncertainty of manufacturing environments emphasizing the need for robust heuristics and heterogeneous response time requests of customer orders, this thesis revisits priority scheduling research and applications. Scheduling rules are studied in a variety of statistically generated job shop environments in which the task is to allocate resources to the individual operations of orders that are known to decision-makers. The performance of the priority index rules is analyzed in production systems where dispatching decisions are postponed and no idle time is inserted (non-delay scheduling). The fundamental question addressed is whether it would be possible to identify a single dominant rule to be considered as the basis for a standard scheduling protocol instead of testing different rules to find some fitting ones for each particular problem instance. In addition to the consistent comparison of priority rules, this thesis examines different technical specifications and tolerances for information and communication necessary to implement scheduling rules and illustrates the sensitivity of system performance to some alternative scheduling conventions. The search for a theoretically justified and managerially applicable priority rule which could form the core of a standard scheduling protocol for integrated order management is reported in two parts. First, insights into the rationale and tardiness behavior of all reasonable priority index rules identified from the prior research are provided by analyzing the results of large-scale simulations in a variety of relevant job shop settings. It is demonstrated that, in fact, there is not just one rule but a whole family of dominating rules. These look-ahead rules (ATC, COVERT, and CR+SPT) strike a balance between local anticipation of job tardiness, through different types of look-ahead features, and global coordination of machine utilization through rational lead time estimates. Certain conditions of the shop and the selection of performance criteria, including order-specific costs for tardiness, inventory holding, and expediting, may favor one of these look-ahead priority rules over the others, thereby suggesting a trade-off between the informational complexity of the index and the eventual impact of the inherent coordination principle. Second, tests of different cases of implementation practices provide comforting results for the practitioners worrying over the accuracy of information used in lead time estimation and order priority determination. The look-ahead rules are not very sensitive to the selection of lead time estimation methods, nor errors in cost and processing time estimates. Furthermore, the benefits of using detailed estimates of tardiness penalties and operation-specific data are confirmed. New results indicate the superiority of the look-ahead rules when compared to the use of additional order release mechanisms and consistent improvement if the look-ahead rules are applied at least at some of the machines in the shops. Another additional benefit is the predictability of the on-time progress of orders through the shop. The contribution emerging from the systematic and thorough examination of the inherently complex scheduling problems is a remarkably simple yet novel platform for evaluating the conditions for efficient coordination of priority dispatching rules. First, the benchmarking framework summarizes the intuitive results of dispatching research for managerial applications by matching the complexity and rationale of rules with requirements of problems. Second, the preliminary specification of, and experiments with, priority scheduling protocols set the stage for the future studies and large-scale applications of dispatch priority rules. Overall, this thesis provides a deeper understanding of the mechanisms of dispatching – instead of testing yet another rule – to facilitate a fruitful dialogue between managers and scholars. The agenda for future research still includes implementation issues of standard order scheduling protocols and the specifications of new classes of scheduling problems emanating from services and supply chain management.
Supervising professor
Vepsäläinen, Ari P.J., professor
Other note
Permanent link to this item