Limited Re-Sequencing for Mixed-Models with Multiple Objectives, Part II: A Permutation Approach ()
1. Introduction
Prudent production scheduling has long been a means for enhancing the competitive position of the manufacturing firm. Effective scheduling can be used to enhance flexibility in a Just-in-time (JIT) system, as well as reduce the required number of setups associated with changeovers. These two entities (flexibility and required number of setups) are of paramount concern here. Many past research efforts have confirmed the fact that these two entities are inversely related to each other. In other words, a strong performance of one suggests a poor performance of the other.
Another caveat related to production sequencing relates to the fact that there are frequently several individual processes involved in the aggregate production function. For each individual process, it may be possible to “re-sequence” the production sequence used in the prior stage of production. This re-sequencing may, if properly done, induce some efficiencies that were not present before re-sequencing. Exploiting the multiple processes with the intent of performing well with regard to both number of setups and flexibility is a facet of production research that has not been explored to any reasonable degree.
This research addresses the production sequencing problem in a JIT environment where the number of setups and the flexibility of the sequences are simultaneously considered for multiple processes. Two heuristics are presented to accomplish the sequencing—both are rooted in a Monte-Carlo simulation selection process. The first employs a selection process rooted in performance potential, the second employs the same selection process as the first, but is also weighted in the spirit of Ant Colony Optimization [3]. For a set of problems from the literature, the performance of the heuristics is assessed against optimal, and against a search heuristic from a prior research effort [2].
Via development of a detailed example detailing the concept of limited re-sequencing and capturing the efficient frontier, the sequencing methodology is presented, an experiment is described, analyses of performance are made, and general observations are offered.
2. Sequencing and Limited Re-Sequencing
2.1. Setups vs. Flexibility
To better understand the idea of multiple objectives and multiple processes, consider a trivial problem that requires two units of item A, one item of item B, and one unit of item of C to be placed into a production sequence. On possible sequence is AABC. This sequence results in (3) changeovers, which is the minimum value possible. Unfortunately, this sequence does not propagate flexibility—there is an uneven flow of items through the sequence, in proportion to demand, resulting in a high usage rate (2.75) as presented by Miltenburg [1]. Although the usage rate is formally defined in the methodology section, an informal description is provided here. Consider a hypothetical situation where the two units of A, and single units of B and C are required for the customer’s to assemble. If the total number of demanded assemblies is 10,000 units, then 20,000 units of A would be required, with 10,000 units of both B and C required. Suppose the schedule is to produce the 20,000 units of A, followed by the 10,000 units of B, and finishing with the 10,000 units of C. This sequence would result in (3) setups—the minimum possible amount. Consider next, some sort of disaster, such as a massive power outage, occurring immediately after the 20,000 units of A were produced. These completed units of item A are of no value to the customer, because items B and C are unavailable and required for the assembly. This hypothetical scenario illustrates a lack of flexibility, underscoring the importance of “inter-mixing” the individual items as much as possible—an important feature of JIT systems.
One sequence that would better propagate flexibility is ABAC. This sequence has a better measure of usage (1.75) than does AABC. Unfortunately, this sequence requires (4) setups, more than the (3) associated with the AABC sequence. This scenario illustrates that a sequence boasting flexibility can result in more setups than a sequence involving less flexibility. This inverse relationship between required setups and flexibility (measured via Miltenburg’s usage rate) is a complicating force in production scheduling.
2.2. Multiple Processes
Another complicating force is the requirement of multiple processes. Consider the above example applied to multiple processes. For the purpose of this illustration, it is assumed that (10) processes are required. The AABC sequence would then require (30) setups in all, with an aggregate usage measure of 27.5. The ABAC sequence would require (40) setups, with an aggregate usage measure of 17.5. The AABC sequence provides desirable setups, but undesirable flexibility, while the ABAC sequence provides just the opposite returns.
2.3. Limited Re-Sequencing
It appears that the multiple processes further amplify the tradeoff between setups and flexibility. This need not be the case if one were to “re-sequence” items between the different processes. In this context, re-sequencing means that one item is taken out of the sequence, and re-inserted into a later part of the sequence. Consider the following example of re-sequencing, where item B (underlined) is re-inserted into a later part of the sequence.
AABC (Original Sequence)
AACB (Modified Sequence)
In the example above, item B was physically removed from the sequence, held in a buffer, and later re-inserted [4]. This type of re-sequencing suggests the assumption that there is physical space available that permits one to hold an item in a buffer until a later time. Specifically, this research does permit a buffer size of one unit, essentially meaning that one unit can be held and later re-inserted in the sequence. A side effect of this assumption is that units not held in buffer can move up no more than one sequence position. Below is an example of a forbidden sequence modification:
AABC (Original Sequence)
BCAA (Modified Sequence)
The above scenario is more permitted because both of the items A would have been held in buffer (exceeding the buffer size of one), causing the B and C to move up more than one position in the sequence. Finally, it is permitted to have more than one modifications made in a sequence, provided that there is never more than one unit held in buffer at a time. Here is an example of this:
ABAC (Original Sequence)
BACA (Modified Sequence)
The above sequence modification is permitted because there is at most one unit held in buffer at any time (it is item A in this example). The first item A is held in buffer and is re-inserted after item B. The second item A is held in buffer and is re-inserted after item C. Note that neither items B or C more up more than one sequence position. This re-sequencing preserves diversity in the continuum of feasibility [5].
2.4. Seeking an Efficient Frontier
As stated earlier, the minimum setups sequence is AABC, resulting in (3) setups and a usage rate of 2.75. Another sequence is ABAC, resulting in (4) setups and a usage rate of 1.75. Applied over (10) total processes, AABC yields 30 total setups and an aggregate usage of 27.5. The ABAC sequence, over (10) processes yields 40 total setups and an aggregate of usage of 17.5.
In the interest of multiple objectives, it is germane to seek sequences that find some “middle ground” between the extreme values of setups and usage rates. This “middle ground” can be found via an efficient frontier. In the context of this application, an efficient frontier is intended to describe the minimum usage rate for each unique number of setups for the total number of processes. For problems such as this, where one objective is of a discrete nature (number of required setups) and the other is continuous (the associated usage rate), an efficient frontier works well.
Finding this efficient frontier is a non-trivial task, and is, in effect, one of the main contributions of this research effort. In order to find the efficient frontier, one must find the set of sequences that yield the minimum total usage rate for their associated number of required setups/changeovers. For this research, the “trivial,” or “level-0” sequence will always be the one with the item As at the head of the sequence, followed by the items Bs, etc. For each process required, the prior level’s sequence is subjected to limited re-sequencing as described above. One of the candidate sequences is selected and this process continues until the desired number of levels has received proper attention.
There are essentially two general ways of capturing the efficient frontier. One way is via enumeration, the other way is via some heuristic search. The enumerative approach is guaranteed optimal, but expensive in terms of effort. The heuristic approach is not guaranteed optimal, but if wisely pursued, it can provide near-optimal results with a reasonable effort. For an enumerative effort, one must traverse a search tree, where the nodes are the parent sequence, and the branches are the feasible child sequences of the parent sequences. For the child sequences to be feasible, they must have their sequence members move up at most one position in the sequence. For example, the “level-0” sequence of AABC only has four feasible child sequences: AABC, AACB, ABAC and ABCA. Each of these child sequences then exist at level 1, and each of these are then considered parent sequences for level 2, etc.
Figure 1 shows cumulative usage and setups through each path of the traversal. While the required setups are easily understandable, usage rate is less so, and is discussed in the methodology section. For now, the usage rates and setups are shown in Table 1 for all twelve possible permutations of the AABC problem.
Also shown in Table 1 is information regarding feasibility of child sequences descending from parent sequences. A mark of “1” indicates feasibility from parent to child sequence, a mark of “0” indicates infeasibility. For example, the above elaboration of the feasible child sequences of AABC are noted with marks of “1” in Table 1 (shaded—“ID” tags must be referenced).
If the traversal process were continued through ten processes, the efficient frontier would appear as shown in Figure 2.
While inspection of Figure 2 shows the graphical relationship between setups and usage rate, Table 2 shows the specific sequences that make up the efficient frontier. Here, the interested reader can see the exact sequences that make up the efficient frontier. For example, the combinations of sequences that comprise the lowest usage for 39-setups are BAAC for Level 1, ABCA for Level 2, etc.
2.5. Combinatorial Explosion
Figure 1 shows the traversal details that are essentially required to find the efficient frontier through two levels. Even for two levels, the effort is consequential. Level 0 has a single node, Level 1 has four nodes, Level 2 has twenty-nodes. This illustrates a combinatorial explosion.