Lot PDF Free Download

admin 10/13/2021
LotLot PDF Free Download

Lot Pdf Free Download Windows 10

Lot pdf free. download fullDownloadA lot like love pdf free download

Lot sizes and setup frequency with learning in setups and process quality. Suresh C H A N D Krannert Graduate School of Management, Purdue University, West Lafayette, IN 47907, USA. Abstract: Supporters of the Stockless Production Philosophy have argued that the traditional Economic. Order Quantity approach leads to large lot sizes because it. Due to a planned power outage, our services will be reduced today (June 15) starting at 8:30am PDT until the work is complete. We apologize for the inconvenience.

45+ Download Resume Templates – PDF, DOC. Free Download Professional Resume. Always keep in mind that you do not need to provide a lot of contact details. Free PDF Creator & Converter 100% free PDF Creator & PDF Converter. The 100% free PDF Creator and PDF Convertor supplied by pdf24.org works with all Windows programs and has a lot of features you wouldn't expect from free software: create PDF files from almost any Windows application, re-order pages, merge, split, and password-protect your existing PDF files. Lot-by-lot inspection 1 Scope 1.1 This part of ISO 2859 specifies an acceptance sampling system for inspection by attributes. It is indexed in terms of the acceptance quality limit (AQL). Its purpose is to induce a supplier through the economic and psychological pressure of lot non-acceptance to maintain.

A Lot Like Love Pdf Free Download

354
European Journal of Operational Research 75 (1994) 354-364 North-Holland
Feasibility of scheduling lot sizes of two frequencies on one machine Dr. Celia A. Glass Faculty of Mathematical Studies, University of Southampton, Southampton S09 5NH, UK Received August 1992; revised February 1993
Abstract: This p a p e r considers the Economic Lot Scheduling Problem of finding a feasible schedule that allows cyclic production of several products on a single facility so as to minimise holding and set up costs. We consider the case when products are produced in a given fixed lot size and at regular intervals with at most two cycle lengths between them. Our main results are, for the multi-product case: necessary and sufficient condition for existence of a feasible schedule; a method of constructing a feasible schedule; and necessary and sufficient conditions for 100% utilization of the production line; and for the two product case: a characterization of all feasible schedules. It is envisaged that the results will be used to help construct production schedules which utilise the production line well and keep down holding costs, by using two regular intervals. Keywords: Production/scheduling; Feasibility testing; Economic Lot Scheduling Problem
1. Introduction This p a p e r considers the Economic Lot Scheduling Problem of finding a feasible schedule that allows cyclic production of several products on a single facility so as to minimise holding and set up costs. The problem is a difficult one and there have been many papers written on the subject including an excellent review by E1maghraby (1978). In this p a p e r we restrict our attention to the problem of identifying when it is feasible to combine production plans of several products on one machine assuming that batches of each product are of fixed size and are required to be produced at given regular intervals. In this way the explicit consideration of inventory costs, set up costs, demand and stock levels are bypassed, while account is taken of times to set up the machine when it switches from one product to another. However, provided we develop a test
Correspondence to: Dr. C.A. Glass, Faculty of Mathematical Studies, University of Southampton, Southampton SO9 5NH, UK.
for feasibility which is easy to apply, our results might be incorporated into an algorithm aimed at minimizing costs.
1.1. Background Any solution to the Economic I.xgt Scheduling Problem involves first fixing the cycle length of each product, or equivalently the lot size, which determines the length of a production run of each product including set up times, and then finding a schedule of the resulting production cycles in which two or more production runs do not overlap. The latter is often impossible to do even when the aggregate requirement for time on the production line is relatively small. Clearly, the two parts of the process are intimately related. Hsu (1983) has shown that even the General Feasibility Problem: how to test if a feasible schedule exists for any number of production cycles, is NP-complete and hence the existence of a polynomial time algorithm for solving this problem is unlikely. This does not mean to say that it is an intractable problem for a small n u m b e r of
0377-2217/94/$07.00 © 1994 - Elsevier Science B.V. All rights reserved
SSDI 0377-221 7(93)E0199-8
C.A. Glass / Feasibility of scheduling lot sizes of two frequencies on one machine
products. Any simple solution to the feasibility problem for particular cases would facilitate the choice of lot sizes within a stock control or cost model. An early, obvious approach is to minimise stock holding and set up costs for each product by routine application of the economic lot size approach. But it is frequently impossible to find a schedule of the resulting production cycles. To ensure feasibility a common cycle length may be chosen as in the C o m m o n Cycle approach of Hanssmann (1962). Other similar approaches, described in Elmaghraby's review p a p e r (1978), are the Basic Period approach due to Bomberger (1966) and the Extended Basic Period approach due to Elmaghraby himself (1978). Other, more recent, approaches involve dropping one or more of the restrictive assumptions of this problem. Dobson (1987) for example, develops a formulation that provides feasible schedules by allowing the lot size, and thus the cycle times, for each product to vary over time. Another approach in which absolute regularity of cycle lengths is dropped is discussed by Matthew (1988). It involves defining a sequence, called the fundamental cycle, in which every item is made at least once. Vemuganti (1978) gave a concise, necessary and sufficient condition for feasibility in the two product case. For three or more products with integral frequencies he constructed a mixed integer linear program (MILP) formula to test for feasibility. Glass (1992) gives necessary and sufficient conditions for feasibility in the three product case. In Hsu (1983) the M I L P formula in three product cases is further illustrated. Hsu developed an implicit enumeration procedure using graph theory as an alternative approach. The latter approach has the distinct advantages of producing a set of maximal feasible partial solutions and being capable of manual solution if there are few products. 1.2. Structure o f p a p e r
In this p a p e r we develop a n u m b e r theoretic approach to this problem which involves examining start and end times of production runs and is by its nature constructive. We start with the case of two products, illustrate how Vemuganti's feasibility test arises, and give an intuitive explanation.
355
Our approach gives rise to a classification of all feasible schedules if one exists. This approach is then extended to a limited number of extra products of one or other frequency. For more products the problem is reduced to a different form which is amenable to well-studied algorithms. Utilization of the production line is then examined and possible extensions to this work discussed. The approach is illustrated by a few examples.
2. Results for the two product case
The two product case has been explored by Vemuganti (1978) and he derived a test for feasibility which is given below in T h e o r e m 1. We develop an alternative approach, as it gives much insight into the problem and leads to a method of construction and complete classification of the set of feasible solutions (if one exists) in T h e o r e m 2. Examples are given in the next section, and the reader might find the proofs of T h e o r e m 1 easier to follow by reference to the illustrations of these examples. Our approach relies heavily on a fundamental theorem of arithmetic given in the Appendix. By the nature of the problem any feasible production schedule is cyclical, for example being repeated at regular intervals of a year. It is therefore irrelevant for the mathematical solution of the problem where the cycle is considered to start or if it runs in reverse. The following notation will be used throughout this paper.
Notation
i = Product index. o-i = The length of time product-i takes for each run on the production line, i.e. production time plus set up time, in terms of one total production cycle. n i = The number of runs of product-i in the total production cycle. (o'i, n i) = The production pattern in which there are n i regular production runs of product-/ each of length ~ri. Res(a, m ) = Residue of a modulo m (for integers a, m), i.e. O~<=' and='>
356
C.A. Glass / Feasibility of scheduling lot sizes of two frequencies on one machine
Res(a, m ) m o d u l o m. gcd(a, b ) = Greatest common divisor of integers a and b. lcm(a, b) = Least common multiple of integers a and b. When there are just two products: d = gcd(nl, n2). N = lcm(n 1, n2). rI = nl/d. r 2 = n2/d. Theorem 1. (Test of feasibility). A necessary and sufficient condition for two regular production patterns (O-l, n 1) and (0.2, n2) to be scheduled in the same time period is 0'1 + 0'2 ~< lcm(nl ' n2 ) •
the runs of product-1 begin within the production cycle of product-2 at points
(
Res[ ~
Res k, ~
1
do-1 + do.2 ~< - -
rlr 2
1
)
.
0~< />< />
,
1
Icm(nl, n2) '
then the above argument shows that by starting the production cycles with a run of product-1 and following it immediately with a run of product-2 the remaining runs of the two products will not be in conflict on the machines. [] Theorem 2 (Construction and classification of
feasible solutions). If a feasible solution exists, then any schedule of the following form is feasible: start with a first run of product-I; follow it by a gap of length y, where
I
is equivalent to
l -
since n 2 / d and n l / d are relatively prime. Therefore a run of product-1 and a run of product-2 must be able to share one time unit of length, which is ( 1 / N ) - t h of the total production cycle, for there to be a feasible schedule. Conversely, if
(1)
Proof. Observe that, it is not strictly necessary to give a proof of T h e o r e m 1 for any case other than when n I and n 2 are coprime, since any feasible schedule for the original problem consists of d repeated schedules each with n i / d runs of product i, of length do'i to this subcycle, for i = 1, 2. In other words feasibility for the pairs {(0'1, nl), (0'2' n2)} is the same as for {(doh, n l / d ) , (do'2, nz/d)}. Moreover,
~l<~n
The fundamental property of arithmetic given in the Appendix tells us that this set is equal to
0'1 -]- 0'2 ~
0--.< />< lcm(nl,=' n2)=' -=' (=' 0=' .=' 1=' +=' 2=' />
1
1
drlr2
lcm(nl, n2)
0.1 + 0.2 ~ - -
nl d
'
However, as the proof is intended to aid construction of schedules it is given explicitly for any integers n I and n 2. We may assume without loss of generality that the production cycle starts with a run of product-1. For convenience we divide the total production cycle into N time intervals. Runs of product-1 begin at times l N / n 1 = ln2/d for l between 0 and n 1 - 1, in these time units. Now divide the total production cycle, starting at time 0, into n 2 equal segments each of length N / n 2 = n J d . Any feasible schedule of product-2 must be fitted into each of these segments in the same place and be between runs of product-1. But, by construction,
)
;
follow that by a run of product-2; and the rest of the schedule is determined. Moreover, any feasible solution not of this form may be derived from one of this form by starting the production period at some other time in the full cycle. Proof. That any schedule of the first form stated above is feasible follows from the proof of Theorem 1, in particular the range within which a run of product-2 is scheduled after a run of product-1. It follows from the remarks at the beginning of this section that any feasible solution not of this form may be derived from one of this form by either (i) starting the production period at some other time in the full cycle; or
C.A. Glass / Feasibility of scheduling lot sizes of two frequencies on one machine
ning of this run of product-2 to realise the required schedule. []
(ii) reversing the production schedule; or (iii) a combination of (i) and (ii). The proof is completed by showing that, in fact, (ii), and hence (iii), are unnecessary, Let 3' denote 1 / l c m ( n l , n 2 ) - ( 0 . 1 +0.2)- Reversing a schedule of the prescribed form results in a run of product-1 starting after a gap of y after a run of product-2, where y is between 0 and 7. Let y ' denote 3' - Y- Then 0 ~
3. Illustration of the approach
We now illustrate our approach with a particular example. Consider the case when n l = 5 and n 2 = 3. Divide the production period into 15 units and schedule product-1 to start a run at time 0, as in Figure la. Then divide the production period into three equal parts, as in Figure lb. Each part is a 0.2-cycle. Superimposing the cycles we get Figure lc. Observe that a run of product-1 occurs in each unit. Product-2 may feasibly be scheduled in any of the gaps in this interval. This can happen only if 0.1 + 0.2 4 6 . Moreover, one run of product-1 must end within ~ - (o'1 + 0.2) of the start of a run of product-l, and provided it does, the schedule will be feasible. Take the case when 0.1_ 0.04 and 0.2 = 0.02. Since 0.1 + 0.2 = 0.06 < 0.066 = g1, feasible schedules exist. Two such schedules are illustrated in Figure 2.
nl mod --~-,
starts at the beginning of a unit immediately following a unit containing a run of product-2. The proof of T h e o r e m 1 shows that such an ! exists. Moreover, by construction, this run of product-2 is followed by a gap of {
~ lcm(nl ' n 2 )
0.1
-y'
--0.2
)
=Y
before the run of product-1. It is therefore sufficient to start the production period at the begin(a)
357
In the total production cycle
O
~
a
_~
_4
_s
15
a5
15
15
t5
6_
fs
Z
rs
_o
Is
Z
15
~o i'~
~s i~
~ f~;
i~ fs
lll
J4
!
(b)
In the production cycle split into three equal parts corresponding to p r o d u c t - 2 cycles
(c)
In superimposed p r o d u c t - 2 cycles
Figure 1. Runs of product-I (when n 1 = 5, n 2 = 3)
C.A. Glass / Feasibility of scheduling lot sizes of two frequencies on one machine
358
Observe that in this schedule the production facility is used very unevenly and only for 26% of the time. However, going back to Figure lb we can see that there is in fact room for five products each with a frequency of 3 provided that none is of length greater than 0.026 ( = 1 _ trl) and two more products of length at most ~r1 with a frequency 5.
that, along with the two products already scheduled in the above example, there is another product with frequency 5 with combined set up and run time 0.03, and another three products with frequency 3 with the following combined run and set up times: 0.015, 0.02, 0.025. Figure 3 gives a feasible schedule, and illustrates how it was constructed. Production line efficiency in this case is 59%.
4. The two frequency, many products case
4.1. Limited number of products
The illustration of the proof for the two product case above suggests how the results may be generalised to a many product case. Suppose (a)
We adopt the following notation for the case of many products, two cycle lengths. Let n~ and
A feasible schedule in s u p e r i m p o s e d p r o d u c t - 2 (i)
(b)
cycles (ii)
A total production cycle split into t h r e e equal parts (i)
(ii)
b~
(c)
A total production cycle (i)
iilt I f
;I
3
I I lii il I I
4.
I:
6
t liiill
7
8
9
10
11
12
• ~s
9 ~
to rs
1
12
f3
111 14
1
(ii)
0
-f
f5
a
a
±
s
~
z
IS
I$
15
rs
f5
f5
13
Figure 2. Two examples of feasible schedules (when n I = 5, n 2 = 3,tr 1 = 0.04 and tr 2 = 0-02)
14'
1
C.A. Glass / Feasibility of scheduling lot sizes of two frequencies on one machine
(a)
The total production cycle
£
(b)
359
The
a
3
production
4-
cycle,
5
split
into
6
7'
8
three
equal
9'
tO
~2
It
13
14.
j.
parts
lill liil I (c)
Superimposed
cycles
of
frequency
3
Figure 3. A feasible schedule for six regular products on cycles: (5,0.04), (5,0.03), (3,0.02), (3,0.015), (3,0.02) and (3,0.025). Key: line shading is used for products with frequency 5, and dot shading is used for products with frequency 3
n 2 d e n o t e a pair of frequencies, tt the n u m b e r of p r o d u c t s with a regular cycle of frequency n~ and t 2 the n u m b e r of products with a regular cycle of frequency n 2. T h e time on the p r o d u c t i o n line (including set up) used by each run is d e n o t e d by 0-11, O'12 , . . . , O ' l t L and O'21 , 0'22 , . . . , 0-2t 2 respectively. T h e test for feasibility for two products generalises to the following results.
Theorem 4.
If
n I
t 2 4 g c d ( n l , n2 )
but
t 1 > g c d ( n t , n2) ,
then the problem reduces to one o f fitting a set o f t l lengths {0-1i l1 <~i <~t 1} into n 2 / g c d ( n p r/z) equal gaps o f length
l c m ( n l , n2) Theorem 3.
n 2
max ~2~ • J
If
n 2
t I ~< g c d ( n l , n2)
n 1
and
t 2~< g c d ( n l , n2) ,
then the necessary and sufficient condition f o r there to be a feasible solution is
T h e case of T h e o r e m 4 may be tackled as a 'bin packing' p r o b l e m discussed in C o f f m a n (1982) or else by m e t h o d s suggested below for the general case.
4.2. General case - A n y number o f products 1 max0-ti + max0-2j ~< i j l c m ( n t, n2)
For the more complicated case w h e n both t~ and t 2 are large, an algorithm would be required
360
C.A. Glass / Feasibility of scheduling lot sizes of two frequencies on one machine
to fit t lengths, {pili = 1. . . . . t} say, into r subsets while keeping the maximum total length of elements in any of the subsets as small as possible, /'({Pi}, r) say. This is the equivalent to the job shop problem, denoted by P / / C m a x , of distributing t jobs to r identical machines run in parallel so as to minimize the overall completion time (Pi in this case denoting processing time of job i on any of the machines). Theorem 5. The general test for feasibility is
F {¢,i}, gcd(nl, n2)
( +F
1 gcd(nl, n2 ) < lcm(nl ' nl
{O'zj},
)
n2 ) .
The P///Cma x problem was shown to be NPhard by Garey and Johnson (1978). However, there are many approximation algorithms which are probably close to optimal. From Theorem 5, it can be seen that it will not always be necessary to have optimal values for the F's. Work done on this problem is surveyed succinctly in Lawler et al. (1990) and with more detail in French (1982). A simple approximation algorithm due to Graham (1969), known as List Scheduling on longest processing time list, put in terms of this problem, is as follows. Algorithm LPT Step 1. Put the lengths {Pili= 1 , . . . , t } in decreasing order. Step 2. Take the longest length not yet dealt with. Step 3. Put it in the least full of the r subsets. Step 4. Return to Step 2.
This algorithm is known to produce a solution whose worst case performance ratio relative to the optimum, LLP'r/F * say, is 4 / 3 - 1/3r, see Graham (1969). Moreover, in the special case when m a x j p j m i n j p j < t / 2 ( r - 1 ) , Ibarra and Kim (1977) have shown that this ratio is reduced to 1 + 2(r - 1)/t. Application of this algorithm will give one of the following cases: Case I: FLPT({o'I,}, r2) + FU'T({o-zj}, ~<
1
lcm(nl, n2) '
rl)
Case II:
(4
FLPT({~rli}, re) 3 >
+
3r 2
1)
FLPT({~re,}, r,) 3
3r 1
1
lcm(nl, n2) ' Case III: Neither I nor II apply. In case I algorithm LPT has given a feasible solution to the original problem. In case II no feasible solution exists since the worst case performance ratio shows that F*({trli}, r 2) + F*({o'2i}, r 1) is bounded below by the left hand side of expression II, and hence Theorem 5 cannot be satisfied. Condition II may of course be strengthened in the special case dealt with by Ibarra and Kim (1977). If III is the case, then the problem is still undecided, and a more sophisticated approximation algorithm may be tried. If the problem is small, one can of course use complete enumeration but this is of order O(rt/r!) as each of the t jobs may be put on any one of the r machines and solutions are equivalent up to reordering of the machines. Graham (1969) suggest a polynomial-time approximation scheme combining complete enumeration with list scheduling algorithm, by optimally scheduling the k jobs with longest processing time and 'list scheduling' the rest. The number k is selected by the criteria of required degree of closeness to optimality and computational complexity both of which Graham analysed. The worst case performance ratio is 1 + ( 1 - 1/r)/(1 + k / r ) and the order of computational complexity is O(tkr). Other approximation algorithms for this problem are due to Sahni (1976), know as 'rounded dynamic programming', and due to Hochbaum and Shmoys (1987), a dual approximation algorithm. Each has known computational complexity and worse case performance ratios.
4.3. Case where frequencies divide nln2/gcd(nl, n2) It is clearly possible to incorporate regular production runs with integer frequencies which divide both n 1 and n z. Products whose frequency divides gcd(nl, n 2) may be accommodated in the spaces between
C.A. Glass / Feasibilityof scheduling lot sizes of two frequencies on one machine
361
26%. When a further three products are introduced in Figure 4, utilization increases to 59%. Utilization of the production line for only two products with different cycle lengths is by necessity limited and an upper bound is given in the following proposition.
runs of items with frequencies n~ or n 2 in the gcd(n~, n 2) subcycle, which has been our focus of analysis above. The only additional flexibility is that of combining runs of the same frequency where that frequency strictly divides gcd(n~, n 2) so that they overlap when the gcd(nl, n 2) subcycles are superimposed. Items whose frequency strictly divide n 1, say, may be included by being scheduled as if they had to occur n~ times in each cycle. However, there is room for savings by combining items with the same frequency (or a divisor) into pseudo items with frequency n]. For example, in the case where n~ = 6 and n 2 = 5 items (0.015, 2), (0.010, 2), (0.026, 2), (0.025, 1) may be incorporated by combining into one pseudo-item (0.026, 6).
Proposition 1. The proportion of time the production line is utilized when scheduling two regular production cycles of frequency n], n 2 is less than m a x ( 1 / r 1, 1~re). Proof. To see this note that total utilization for n~ runs of product 1 and n 2 runs of product 2 is nl~r I + n20-2. This is less than max(n1, n2)(tr 1 + cr2) which itself is no greater than max(n1, n 2 ) / l c m ( n 1, n 2) by Theorem 1. Moreover, in the above notation, max(nl, n 2 ) / l c m ( n l , n 2) is m a x ( 1 / r l, l/r2). []
5. Utilization of production line
Thus the 26% utilization of example 2 is fairly close to the theoretical upper limit of 33.3% for any length production runs o-i, cr2 with frequencies 3 and 5.
In the illustrations about, the utilization of the production line for two products in Figure 2 is
(a) The total production cycle
a
3
4
5
IS
7
8
?
Io
II
tl
(b) The production cycle, split into three equal parts
(c) Superimposed cycles of frequency 3
Figure 4. A full schedule of three cycles(5,0.04) and five cycles(3,0.026)
t3
t4
1
362
C.A. Glass / Feasibility of scheduling lot sizes of two frequencies on one machine
By contrast, however, there is no theoretical limit on utilization imposed by restricting production runs to two frequencies provided that the number of products/sublots is not restricted. Figure 4 illustrates a completely utilised production line accommodating five production runs of frequency 3 and three production runs of frequency 5. Precise conditions under which complete utilization may occur are formalized in Proposition 2 below.
Proposition 2. Necessary and sufficient conditions for a production line to be completely utilized by many products {05i [i = 1. . . . . tl}, {cr2j ] j = 1. . . . . t 2} with two cycle lengths, n l, n 2 respectively, are: (i) the times (0-1ili = 1 . . . . , t 1} may be partitioned into r 2 subsets o f equal total duration, F1, say; (ii) the times {~r2j I j = 1 . . . . , t 2} may be partitioned into r I subsets o f equal total duration, F 2 say; and (iii) F 1 + F 2 = 1/lcm(nl, n2). Proof. Suppose that the three given conditions hold. Let Au denote the combined production line time of items in the l-th subset of product-1 items, for l = 1 , . . . , r 2. Each Au equals F 1. Define Azk, for k = 1 , . . . , r 1, similarly. Each A2k equals F 2. Property (iii) ensures that
maxi
Ali 'F maxj A2j ~ F 1 + F 2
1 lcm(nln2 ) ,
and hence, by Theorem 3, there is a feasible schedule of these items. Moreover, in each 1/lcm(n~, n 2) subinterval there is precisely one pair of composite runs A~i, A2j (for i = 1. . . . , r 2 and j = 1 , . . . , rl). Since Ali + A2j =/'1 + F2
lcm(n, n2)
for each i and j, the schedule has no gaps and thus completely utilizes the production line. Suppose now that {o-it} and {o-2k} may be scheduled to completely utilize the production line. We shall use the construction of the proof of Theorem 1 to analyse the properties of the crij. Consider the subschedule got by superimposing
cycles of frequency 2. Each item with frequency 1 occurs r 1 times at intervals of (1/lcm(nl, n2))-th of a full production cycle, while each item with frequency 2 occurs precisely once. Take an item with frequency 1 and consider the r~ intervals between its runs in this superimposed schedule. Each interval is occupied for exactly the same amount of time by items of frequency 1 and therefore has exactly the same amount of time, F 2 say, used by runs of items of frequency 2 (since there is no idle time in this schedule). Thus the times {o2j I j = 1. . . . , t 2} split into r I subsets of equal total duration which we have called /'2, and property (ii) is satisfied. By symmetry property (i) must also hold. By construction, F~ and /'2 are the amount of time used by items of frequency 1 and of frequency 2 respectively in a 1/lcm(n~, n2) subinterval of the total cycle. Property (iii) now follows from the fact that the schedule completely utilizes the production line. []
Complete utilization may also be achieved by inclusion of cyclic runs with frequencies (including 1) which divide n l n 2 / g c d ( n l , n2), discussed in Section 4.3 above.
6. Extensions While it has been assumed in this paper that the cycle lengths of production runs are fixed, it is envisaged that the results will be used to help determine appropriate cycle lengths by providing a simple test for feasibility of combinations of regular production cycles. This approach needs to be tested on some real production scheduling problems. A natural extension of the results presented in this paper is to the case of three or more products with at most three (or more) frequencies between them. This is a topic of current research by the author. The three product, three frequency case is presented in Glass (1992). Other possible extensions are: to add 'irregular' production runs to the final schedule (e.g. in the gaps in the production schedule described by our algorithm); and to allow extra flexibility by dividing the total cycle into slightly smaller units (suggested by M. Bramwell).
C.A. Glass / Feasibility of scheduling lot sizes of two frequencies on one machine
7. Conclusion
which is equal to
In this paper we have analysed the Feasibility Problem within the Economic Lot Scheduling Problem for several products with at most two distinct frequencies. In the case of two products, a characterisation of all feasible schedules was arrived at. The necessary and sufficient condition for, and construction of a feasible schedule was extended to certain cases of several products with at most two frequencies between them. For the general case of any number of products with at most two frequencies between them the problem was r e d u c e d to the scheduling problem, P ~ / C . . . . of allocating jobs to identical parallel machines so as to minimize the overall completion time. This problem is well studied and although it is NP-complete there are good approximation algorithms for finding a solution (e.g. List Scheduling) which will often suffice for our purposes. Utilization of the production line was also examined, and it is shown that 100% utilization may be achieved. Our method of constructing schedules gives insight into the nature of the problem. In particular, it shows how to pack a production line with several products but a restricted number of frequencies. This may be greatly exploited in practice. These results might be incorporated into models of inventory levels and of costs of holding inventory and of setups to solve the Economic Lot Scheduling Problem or generalizations thereof.
{Res(kd, a) IO ~Appendix Theorem A.1. The greatest common divisor, d, of two integers a and b may be represented as the difference between multiples o f a and b, that is, d = a x - by for some integers x and y.
Corollary A.1. I f d is the greatest common divisor o f natural numbers a and b, then the set {Res(lb, a ) ] 0 ~<~a=' -=' 1}=' is=' equal=' to=' the='>
I
a)
R e s ( k d , a ) I 0 ~<=' ~=' -='>
363
These results and proofs may be found in Davenport (1970), they follow from Euclid's Algorithm of greatest common divisors.
Acknowledgements The author is indebted to Mr. Z. Zhang, visiting academic from Wuhan University of Technology, P.R. China, for bringing this problem to my attention and for many useful discussions. I also wish to thank an anonymous referee for suggestions which have improved the quality of this paper.
References Bomberger, E.E. (1966), 'A dynamic programming approach to a lot size scheduling problem', Management Science 12/11, 778-784. Coffman, Jr., E.G. (1982), 'An introduction to proof techniques for bin-packing approximation algorithms', in: M.A.H. Dempster et al. (eds.), Deterministic and Stochastic Scheduling, D. Reidel, Dordrecht, 245-270. Davenport, H. (1970), The Higher Arithmetic, 4th. ed., Hutchinson & Co, London, Chapter 1. Dobson, G. (1987), 'The economic lot scheduling problem: Achieving feasibility using time-varying lot sizes', Operations Research 34/5, 764-771. Elmaghraby, S.E., (1978), 'The Economic Lot Scheduling Problem (ELSP): Review and extensions', Management Science 24/6, 587-598. French, S. (1982), Sequencing and Scheduling, Ellis Horwood, Chichester, UK. Garey, M.R., and Johnson, D.S. (1978), 'Strong NP-completeness results: Motivation, examples and implications', Journal of the Association for Computing Machinery 25, 499-508. Glass, C.A. (1992), 'Feasibility of scheduling lot sizes of three product on one machine', Management Science 38, 14821494. Graham, R.L. (1969), 'Bounds on multiprocessing timing anomalies', SIAM Journal on Applied Mathematics 17, 4 ! 6- 429. Hanssmann, F. (1962), Operations Research in Production and Inventory, Wiley, New York, 158-160. Hochbaum, D.S., and Shmoys, D.B. (1988), 'A polynomial approximation scheme for machine scheduling on uniform processors: Using the dual approximation approach', SIAM Journal on Computing 17, 539-551.
364
C.4. Glass / Feasibility of scheduling lot sizes of two frequencies on one machine
Hsu, W.L. (1983), 'On the general feasibility test of scheduling lot sizes for several products on one machine', Management Science 29/1, 93-105. Ibarra, O.H., and Kim, C.E. (1977), 'Heuristic algorithms for scheduling independent tasks on nonidentical processors', Journal of the Association for Computing Machinery 24, 280-289. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B. (1993), 'Sequencing and scheduling: Algorithms and complexity', in: S.C. Graves et al. (eds.), Handbooks in Operations Research and Management Science, Volume 4: Logistics of Production and Inventory, North-Holland, Amsterdam.
Matthew, J.P.S. (1988), 'The optimality of the 'Zero-Switch' rule for a class of economic lot-scheduling problems', Journal of the Operational Research Society 39/12, 11551161. Sahni, S. (1976), 'Algorithms for scheduling independent tasks', Journal of the Association for Computing Machinery 23, 116-127. Vemuganti, R.R. (1978), 'On the feasibility of scheduling lot sizes for two products on one machine', Management Science 24/15, 1668-1673.
< />< />