|
...in the slots of the tool magazines, and the machine works periodically, for example, 5 days a week. Basically the available capacity of every period is the same.
The jobs are divided into two groups, urgent and non-urgent. Those requiring immediate attention are called urgent jobs and the others are non-urgent jobs. We know all necessary information concerning non-urgent jobs before the first scheduling period(day) of a fixed time interval, for example, the first half year. This information can be obtained from the contracts signed by customers and the factory with sufficient lead time to allow pre-scheduling of these jobs. At a given point in time some jobs have been completed and the remaining ones await processing. A past period cannot be considered again to process the waiting jobs, and non-urgent waiting jobs can be rescheduled for future periods as necessary. One objective of the factory is to process all the jobs as soon as possible.
Urgent jobs arrive randomly in each period, and are usually very important to the factory. Therefore the factory always gives them a top priority, to be processed immediately in the current period. Consequently remaining capacity in the current period will be reduced when urgent jobs arrive, and all the waiting jobs must be rescheduled.
Obviously, urgent jobs may be easily scheduled, but the challenge is to fully use the remaining capacity to finish the non-urgent jobs as efficiently as possible, saving time and money for the factory. This motivates us to focus on how to optimally schedule the non-urgent jobs.
As described above, there are several distinguishing features of the problem that make it interesting. First, the remaining capacity of the current period may differ from those of future periods. Then the remaining capacities of the periods can be treated as a version of on-line scheduling, i.e., the capacity of past periods can not be used again, the remaining capacity of the current period is known based on the capacity required by the urgent jobs, and that of forthcoming periods is unknown. We must decide which jobs should be processed as each period arrives. Finally, the objective is to minimize the number of scheduling periods within which all the non-urgent jobs can be processed.
Basically, a Capacitated Machine Scheduling problem (CMS) can be defined as follows: n jobs with processing times {[p.sub.i], i = 1, 2, ..., n} and setup times {[s.sub.i], i = 1, 2, ..., n} are to be processed on a machine. The machine works periodically t = 1,2,... and has available time [c.sub.t] for each period t. The objective is to process all jobs with minimum schedule length, i.e., time periods. We also call [c.sub.t] the capacity in period t, and [s.sub.i] + [p.sub.i] as the entire demand of job i.
There are two types of production settings considered in this paper: in the first type the machine processes the entire demand volume of a job within one period, and in the second the processing time of a job can be split and processed in different periods. We call the two settings CMS1 and CMS2, respectively. In each period of CMS2, there is a setup time incurred when the machine begins to process its first job at the start of the period or changes to process another job after finishing one job. The setup time is [s.sub.i] if job i is processed first in a period or job i is to be processed after one job is finished.
CMS1 is a variant of the Variable-Sized Bin Packing (VSBP) problem. The standard VSBP problem given by Friesen and Langston (1986) is defined as follows: given a list L = ([a.sub.1], ...,[a.sub.n]) of items, each with item size s([B.sup.2]) > ... > s([B.sup.1]) > and an inexhaustible supply of bins of each size, how can we pack the given items into the bins so that the sum of the sizes of the bins used is minimized? When the maximum entire demand of all the jobs is not greater than the maximum capacity of all the periods in CMS1, we can normalize the capacities and the entire demand by dividing each by the maximum capacity. Then the jobs, the entire demands, and the capacities of CMS1 are equivalent to the items, the item sizes and the bin sizes of VSBP respectively. There are two major differences between CMS1 and VSBP. One is that the capacity of a period can be of any size in (0 , 1] after normalization in CMS1 while there are only 1 different types of bins in VSBP. And the other is the objectives of the two models: to process all the jobs within a minimum number of scheduling periods in CMS1, and to pack all the items using a minimum sum of the sizes of the bins used in VSBP.
Intuitively, CMS2 is better than CMS1 in objective value as it allows more degrees of freedom for schedulers, but it is a little more complex to manage in practice. How much better is CMS2 than CMS1? In which situation is the difference between CMS1 and CMS2 small enough that we can use CMS1 instead of CMS2? In Section 2, we shall present the mathematical models for them and compare them theoretically by determining the worst case performance between the optimal solutions of them. Sections 3 and 4 will present heuristic algorithms for the on-line version of the two models and...
NOTE: All illustrations and photos
have been removed from this article.
More articles from IIE Transactions
The value of information used in inventory control of a make-to-order ..., November 01, 2002
Fabrication and assembly scheduling in a two-machine flowshop. (Techni..., November 01, 2002
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.
|
