|
...factor, since delivering goods to customers on the promised due dates is reflected in customer satisfaction levels. One natural quantification of this goal involves the tardiness measure, where tardiness is defined as the positive lateness of a job if it is delivered after its due date. Tardy deliveries can result in rush shipping costs, and may even force a customer (external or internal) to shut down operations, which will lead to the loss of customer goodwill and future sales, thus damaging a firm's financial situation.
The job shop environment considered in this paper can be described as follows. A set of jobs arrive dynamically at a shop to be processed on a set of machines. Each job consists of a chain of operations, each of which needs to be processed on a given machine uninterrupted for a known amount of time. At any point in time, each machine can process at most one job and each job can be processed on at most one machine. A schedule is an allocation of the operations to the available time intervals on the machines. The scheduling problem addressed is deterministic in the sense that all information is known prior to scheduling.
For the reasons given above, we use the minimization of the Mean Tardiness (MT) as the scheduling objective. The minimization of MT has been used as the primary objective in scheduling job shops in order to meet job due dates (Conway et al., 1967; Baker, 1974). Unfortunately, the MT job shop scheduling problem is NP-hard even for the single-machine case (Du and Leung, 1990). This justifies the large body of research on priority dispatching in an effort to identify simple heuristic rules that are easy to implement and still generate good schedules under certain conditions. To date, priority rules are the most commonly used scheduling methods in practice.
In this paper we present a composite priority rule for scheduling dynamic job shops so as to minimize the MT. The development of the proposed composite priority rule is based on the characteristics of several existing dispatching heuristics. The proposed rule utilizes system and job-related information to generate schedules. It is compared to several well-known priority rules under different experimental conditions, based on simulation.
The rest of this paper is organized as follows. Section 2 consists of a brief literature review with the proposed composite priority rule being presented in Section 3. In Section 4 we describe the experimental conditions. The computational results and discussion are reported in Section 5. Conclusions are drawn in Section 6.
2. Literature review
Let us first present a formal definition of the scheduling problem as follows. Consider a dynamic job shop with m machines and n jobs. Job j has [o.sub.j] operations with deterministic processing times [p.sub.ji], i = 1, 2,..., [o.sub.j]. The operations of any job must be processed in a predetermined sequence on the machines. Without loss of generality, assume that for any job, its operation i precedes its operation k, if i < k. Job j arrives at time [r.sub.j] and is due at time [d.sub.j]. If job j is completed after [d.sub.j], there will be a delay penalty. On the other hand, no penalty incurs if a job is completed on or before its due date. The goal is to schedule the n jobs on the m machines so as to minimize the average delay penalty. In this study, the delay penalty of job j is defined as its tardiness which is equal to max{0, [C.sub.j] - [d.sub.j]}, where [C.sub.j] is the completion time of job j. Therefore, the scheduling objective is to minimize the MT which can be mathematically expressed as:
MT = [n.summation over (j=1)] max{0, [C.sub.j] - [d.sub.j]}/n.
Over the past several decades, many researchers have developed priority rules to attack the problem. Panwalker and Iskander (1977) gave an excellent survey for such rules including the Shortest Processing Time (SPT), Earliest Due Date (EDD) and First-Come-First-Served (FCFS) rules. Many of these rules were originally developed for a single-machine environment and then extended to more-complex shop environments such as the one considered in this paper. In general, simple rules such as EDD and Slack per Remaining Processing Time (S/RPT) have been shown to perform reasonably well for lightly loaded shops but deteriorate in congested shops (Vepsalainen and Morton, 1987). On the contrary, the SPT rule performs poorly for lightly loaded shops and generous due date (or flow) allowances, defined to be the time...
NOTE: All illustrations and photos
have been removed from this article.
More articles from IIE Transactions
Lean Logistics: The Nuts and Bolts of Delivering Materials and Goods., September 01, 2006
Looking for additional articles?
Search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication
name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company
analysis or best practices in managing your organization,
Goliath can help you meet your business needs.
Our extensive business information databases empower business
professionals with both the breadth and depth of credible,
authoritative information they need to support their business
goals. Whether it be strategic planning, sales prospecting,
company research or defining management best practices -
Goliath is your leading source for accurate information.
|
