This paper presents the salient aspects of a simulation-based experimental study of scheduling rules for scheduling a dynamic job shop in which the setup times are sequence dependent. A discrete event simulation model of the job shop system is developed for the purpose of experimentation. Seven scheduling rules from the literature are incorporated in the simulation model. Five new setup-oriented scheduling rules are proposed and implemented. Simulation experiments have been conducted under various experimental conditions characterized by factors such as shop load, setup time ratios and due date tightness. The results indicate that setup-oriented rules provide better performance than ordinary rules. The difference in performance between these two groups of rules increases with increase in shop load and setup time ratio. One of the proposed rules performs better for mean flow time and mean tardiness measures.
Scheduling is the allocation of resources for performing a set of tasks [1]. Resources may be machines in a shop floor, runways in an airport, crews at a construction site or processing units in a computing environment [2]. Tasks may be operations in a shop floor, takeoffs and landing in an airport, stages in a construction project or computer programs to be executed. Proper scheduling leads to increased efficiency and capacity utilization, reduced time required to complete tasks and consequently increased profitability of an organization.
The dynamic job shop scheduling problem (DJSSP) is described as follows [3]. The job shop consists of M machines (work stations) and jobs arrive continuously over time. Each job requires a specific set of operations that need to be performed in a specified sequence (routing) on the machines and involves certain amount of processing time. The job shop becomes a queuing system: a job leaves one machine and proceeds on its route to another machine for the next operation, only to find other jobs already waiting for the machine to complete its current task, so that a queue of jobs in front of that machine is formed. Hence, DJSSP essentially involves deciding the order or priority for the jobs waiting to be processed at each machine to achieve the desired objectives. Scheduling rules or dispatching rules are used for this purpose. Blackstone et al. [4] have presented a review of dispatching rules that are used in job shop scheduling.
One of the standard assumptions in DJSSP is that setup times are included in the processing times. Setup involves the activities such as preparing a machine or workstation to perform the next machining operation. Setups may depend upon the type of job, the type of machine or both. Setup time is defined as the time interval between the end of processing of the current job and the beginning of processing of the next job. Setup time is encountered in manufacturing firms such as printing, plastics manufacturing, metal and chemical processing, paper industry, etc. The typical case in DJSSP is sequence-dependent setup times, where the setup time depends on the job previously processed. A typical example is the manufacturing of different colors of paint. In such cases, improving the schedules by as little as 1% can have a significant financial impact.
The traditional approaches in dealing with setup times are that, either to neglect or to include the setup times in the processing times so as to simplify the problems. These approaches would reduce the complexity of the problem, but often lead to unrealistic results. In the literature on job shop scheduling, attempts have been made to address the problem of sequence-dependent setup times. Further, many of these research works do address the static case of job shop scheduling. Yang [5] presents a review of static scheduling research in which the setup time or cost is of main concern. Allahverdi et al. [6] provide a comprehensive review of the literature on scheduling problems involving setup times (costs). They classify scheduling problems into batch and non-batch, sequence-independent and sequence-dependent setup, and categorize the literature according to the shop environments of single machine, parallel machines, flow shops, and job shops. Mathematical programming methods such as traveling salesman problem algorithm and branch and bound algorithm have been used for solving the static job shop scheduling problem with sequence-dependent setup times [7], [8], [9], [10], [11], [12] and [13]. Even solving small size problems using these algorithms requires a lot of computational efforts under more restrictive assumptions. Chan et al. [14] present an assignment and scheduling model using genetic algorithm-based approach to study the effect of machining flexibility. The operations–machines assignment problem has also been solved by Chan et al. [15] in a flexible job shop, which is a variant of the classical job shop.
Experimentation with computer simulation models makes it possible to compare alternative scheduling rules, test broad conjunctures about scheduling procedures and develop greater insight into the job shop operation. Ramasesh [16] provides a state-of-the-art survey of the simulation-based research on dynamic job shop scheduling. Chan et al. [17] present a review of scheduling studies of flexible manufacturing systems (FMS) which employ simulation as an analysis tool. Chan and Chan [18] present an approach known as pre-emptive approach for the dynamic scheduling of an FMS. In this approach, the dispatching rule (scheduling rule) is changed at a frequency that is varied by the quantity of output produced by the system. Chan and Chan [19] in their paper, report on a simulation study aimed at evaluating the performance of an FMS subject to different control strategies, which include routing flexibilities and dispatching rules. Chan et al. [20] provide an analysis of dynamic dispatching rules for an FMS. There have been a few attempts to study the DJSSP with sequence-dependent setup times. Kim and Bobrowski [21] present a simulation study of a dynamic job shop when sequence-dependent setups exist. The study classifies and tests scheduling rules by considering whether setup time and due date information are used. These scheduling rules are evaluated in dynamic scheduling environments characterized by due date tightness, setup times and cost structure.
This paper focuses on a simulation-based experimental study of scheduling rules for scheduling a typical job shop in which the setup times are sequence dependent. A discrete event simulation model of the job shop system is developed for the purpose of experimentation. Seven scheduling rules from the literature are incorporated in the simulation model. Five new setup-oriented scheduling rules are proposed and implemented. The performance measures considered for analysis are mean flow time, mean tardiness, mean setup time and mean number of setups. The remaining sections of the paper are organized as follows.
Section 2 provides the details of the configuration of the job shop production system considered in the present study. In Section 3, the salient aspects of the simulation model developed are described. This section also includes the description of the scheduling rules. Section 4 presents the details of the experimentation. The results and analysis are provided in Section 5. Conclusions are presented in Section 6.
This paper addresses the job shop scheduling problem in the sequence-dependent setup time environment. A discrete-event simulation model has been developed for a realistic job shop production system. The simulation model has been passed through multi-level verification and validation exercise. The simulation output has been suitably subjected to steady state analysis to ensure that further investigations are free from initial bias. The results indicate that sequence-dependent setup time has a significant impact on the shop performance. Different scenarios characterized by variations in setup time ratios, due date tightness and shop load are investigated. The results can be summarized as follows.
(1)
The setup-oriented rules such as SSPT, JSPT, SIMSET, JEDD, JEMDD, JCR, and JSSPT provide better performance under various shop conditions than ordinary rules. The difference in performance between these two groups of rules increases with increase in shop load and setup time ratio.
(2)
The proposed rule SSPT is found to be performing better for the mean flow time and mean tardiness measures.
Flow time measure is a very critical indicator of the lead time and it also provides important information that can be used for setting the due dates or due date allowances. Moreover, it is proportional to the work in process levels. Mean tardiness is related to customer service or customer delivery performance. Considering these aspects, practitioners need to employ scheduling rules that meet the mean flow time and mean tardiness criteria. The proposed rule SSPT fulfils this requirement.
For the top three promising rules such as SSPT, SPT and JCR, regression-based metamodels have been developed. These metamodels are found to offer a good prediction of the performance of job shop system within the domain of their definition.
The results presented in this paper should be interpreted with reference to the job shop system considered for the simulation study and the experimental conditions described. Hence, there is a need for further research to develop and test new scheduling rules under different job shop conditions. For example, the scheduling rules can be tested in a sequence-dependent environment with system disruptions such as breakdowns of machines. Realistic system constraints such as fixture, tooling, etc., can also be considered in simulation. Taguchi's Design of experiments method can be used for simulation experiments. Taguchi's method helps in reducing the number of experiments when experimentation of a system involves many factors and many levels for each factor. Orthogonal arrays can be used for obtaining the experimental design matrices. The results for the DJSSP can be applied in a flexible manufacturing system (FMS) or computer integrated manufacturing (CIM) environment with appropriate modifications. In the literature, the configuration of the FMS is considered as a network of computer numerically controlled machines with parts of many types moved about by a conveyer or wire-guided material handling system. The random FMS is the equivalent of dynamic job shop in conventional production. It is intended for flexible production in high-variety, low-volume situations. While the change over (setup) times between parts of the same family are minimal in an FMS, the change over (setup) times between different families can be quite significant. Because of its integrated nature, scheduling for an FMS requires additional consideration of material handling systems. These aspects provide promising areas for further research.
