36-3-12 김형태, 한용희95-.pdf547.8KB

1. Introduction

1.1 Motivation

 Today, most high-volume production systems may appear to be old fashioned transfer lines but in fact have become highly flexible, producing a large family of products such as automobiles, electronics, and other consumer goods. One objective of striving for flexibility is to reduce the setup cost or time-to-respond to the ever-increasing diversity of custom-er demands. However, even the most flexible systems may still incur some setup cost in job changes. It is often desirable to change the job sequence to further reduce the setup cost and time.

 Conveyors are the most popular material transfer mecha-nism in high-volume production. Conveyors can transfer large amounts of material with simple motion control and also pro-vide buffer space. However, simple conveyor segments are usually constrained to operate in a First-In-First-Out (FIFO) principle. The sequence of materials on a simple conveyor segment cannot be changed by the conveyor itself. To change the sequence in a conveyor system, one needs special mecha-nisms such as bypass, transfer, and spur. The use of special mechanisms costs money and takes up floor space, especially when transporting large jobs, making it important to mini-mize their use and to maximize their utilization in operation.

 However, diverging conveyor junction points and/or off-line buffers (a conveyor itself can be considered as an on-line buffer) can also be used to change the sequence. Junction points and off-line buffers are frequently observed in manu-facturing facilities and changing the control logic of such equipment is relatively inexpensive. Therefore, using junc-tion points or off-line buffers is preferred to using special mechanisms because of the reduced initial investment cost and floor space usage.

 Use of junction points and off-line buffers to change the job sequence can be found in the paint shop operation of automobile manufacturing where reducing the number of car color changes is desired. <Figure 1> shows a diverging junc-tion with an off-line buffer where a single upstream conveyor feeds a finite sequence of cars into two downstream convey-ors that lead to the paint booth. Each car at the end of the upstream conveyor is allowed to the visit off-line buffer be-fore it is fed to the downstream conveyors. It is desirable that color changes are minimized in the downstream conveyors. In <Figure 1>, the number of setups to paint the five cars can vary from zero to four, depending on the dispatch se-quence at the diverging point. Note that the minimum num-ber of setups becomes two if an off-line buffer does not exist.

<Figure 1> Diverging Conveyor Example

 Our sequencing problem can be defined by the following two sets of elements. First, the design parameters include :

 ∙ number of downstream queues at the junction

 ∙ capacity of the upstream (and downstream) queues

 ∙ capacity of the off-line buffer at the junction-if one exists

 ∙ discipline supported by the upstream queues, the down-stream queues, and the off-line buffer, respectively

 ∙ configuration of the junction.

 Second, the known operational parameters include:

 ∙ attributes of the jobs in each queue,

 ∙ setup cost between consecutive jobs in the downstream queue.

 The operational decision is the dispatch sequence at the junction. The setting of multiple upstream conveyors, multi-ple downstream conveyors and/or storage buffers is com-monly observed in many real-world manufacturing environ-ments, including the case study we conducted, as shown in <Figure 2>. In <Figure 2>, for the car at the end of any upstream conveyor, this car may visit an off-line buffer, or bypass an off-line buffer and go directly to one of the three downstream conveyors. Since the car visiting off-line buffer will be ready to be released to one of downstream queues after some time, based on the queue discipline and transfer time of the off-line buffer, the off-line buffer can be used to further reduce the number of color changes.

<Figure 2> Multiple Incoming and Outgoing Conveyors with an Off-line Buffer

 While an optimal or a near-optimal solution may be found by observation for the problem of minimizing the number of color changes in <Figure 1>, finding an optimal solution becomes very difficult when the number of incoming cars increases in a more complex junction. The objective in pro-duction also may include minimizing cycle times or work in process. As can be seen, the minimization of setup alone is rather complex and therefore this paper is restricted to part of the conveyor system design and control with the objective of minimizing setup costs. More specifically, we restrict our attention to a constrained sequencing problem having one up-stream (incoming) conveyor (queue) and no off-line buffer.

1.2 Problem Statement

 Consider the problem of constrained sequencing of a finite set of jobs on a conveyor system with the objective of mini-mizing setup cost. A setup occurs whenever two consecutive jobs do not share the same attribute at a processing station served by the conveyor system. The conveyor system con-sists of FIFO conveyor segments and special mechanisms such as junctions and off-line buffers. A junction is an inter-face between M upstream conveyors and N downstream con-veyors with or without an off-line buffer. It is assumed that M=1 and N>1 with or without an off-line buffer. Time- based measures such as cycle time are not considered.

 The organization of this paper is as follows. Relevant liter-ature is reviewed in Section 2. Related problems are defined and analytical solution methodology is proposed in Section 3. Our research contributions are summarized and future re-search directions are discussed in Section 4.

2. Literature Review

 Morley and Schelberg [36], Morley [34], and Morley and Ekberg [35] discussed algorithms for assigning trucks to paint booths in a truck facility to minimize total make-span and the number of paint flushes. They applied market-based bid-ding algorithms to a GM plant and reported a 100% increase in average color block size in their case study. Their heuristic method turned out to have many advantages - easy to imple-ment, robust with respect to schedule changes or machine breakdowns, and effective reduction of paint changeovers. Campos et al. [12] compared Morley and Ekberg’s mar-ket-based approach with an ant-inspired response threshold algorithm and used a genetic algorithm for getting parameter values for the above two algorithms. Kittithreerapronchai and Anderson [29] simulated a market-based algorithm as well as an ant-inspired algorithm. They found that some parameters in each algorithm could be removed since they are very in-sensitive to the objective function value. All the above ap-proaches use artificial intelligence (AI) techniques to tackle the constrained sequencing problem. These AI approaches are easy to implement and robust to system disruptions such as paint booth breakdowns.

 Atassi [3] proposed the use of temporary re-sequencing, facilitated by an automated storage and retrieval system (AS/RS). The AS/RS acts as a buffer that can store cars before and after painting. Using this buffer, a plant can per-turb the order for painting cars to create larger paint blocks and then restore the original sequence after painting. Myron [38] examined the effect of forming large blocks of cars with the same color at an automotive assembly plant. Using dis-crete event simulation, he showed that a simple block pro-tection rule could significantly reduce setup cost when it is coupled with pre- and post-sequencing using a fully flexible AS/RS.

 However, AI or simulation approaches have the drawback of an inability to provide any optimality guarantee or upper or lower bound. In optimization modeling approaches, Choe et al. [16] was the first to model the constrained sequencing problem as an optimization problem and to get a upper bound. He used an AS/RS to increase the size of paint blocks while maintaining a workload-balanced vehicle sequence. More specifically, the problem is how to perturb the original car flow around the vehicle painting station to reduce color setup with the constraint of not violating maximum allowable deviation from the original sequence. He modeled the prob-lem as a traveling salesman problem with time windows, and succeeded in reducing the model to a manageable size and getting very tight bounds - empirically within 2.5% of optimality - by exploiting the special problem structure. He also discussed various relaxations of the problems for getting a near-optimal solution within a reasonable time. To our knowledge, he was the first to model the color change reduc-tion problem using an optimization formulation. However, his model is different from the models in this research in that he used an AS/RS while we use diverging conveyors as well as off-line buffer to re-sequence the incoming cars.

 A similar setup reduction problem with constrained se-quencing occurs in rail classification yards. In rail classi-fication yards, freight cars are separated, sorted according to their final destination, and assembled to form new out-bound train blocks. Because the classification process re-quires considerable resources, one of the objectives is to min-imize reclassification. Typically, cars with different final des-tinations but sharing some initial portion of their trips are assembled into blocks. In each rail classification yard, blocks are built and staged on classification tracks where they wait for the departure of an outbound train. The list of potential blocks that may go into each outbound train is specified by the makeup policy. Therefore, one needs to send each to the appropriate classification track based on the sorting strategy. In this rail classification problem, if a block at the converging junction fails to join the desired train, it re-circulates back to the diverging junction (called ‘re-hump-ing’). Therefore, the rail classification problem can be re-garded as a special case of the constrained sequencing prob-lem with a diverging junction and a diverging/converging junction shown in <Figure 3>.

<Figure 3> The Rail Classification Problem as a Special Case of the Constrained Sequencing Problem

 The rail classification problem is similar to the constrained sequencing problem to be addressed in this research in terms of the decisions to be made. However, it has two different features as follows. First, departing and arriving train schedule constraints as well as the capacity of each classification track should be explicitly considered. Second, the number of chang-eovers should be counted on the rail for re-humping, not on the rail exiting the classification yard because attaching any ‘wrong’ car in a departing train is now allowed.

 This topic was explored by Siddiqee [43], who compared four sorting and train formulation schemes in a railroad clas-sification yard. Yagar et al. [47] suggested a dynamic pro-gramming approach as well as a screening technique to opti-mize sorting and assembly operations. The relative perform-ance of different multistage sorting strategies were inves-tigated by Daganzo et al. [21]. Each classification track is assigned several blocks and cars should be resorted during train formulation in multistage sorting. They derive equations for the service time per car of triangular sorting in classi-fication yards. Three papers written by Daganzo (Daganzo [18], Daganzo [19], and Daganzo [20]) also analyze and compare different classification strategies and give expressions for the switching work and space requirements. Dynamic blocking, in which the assignment of blocks to classification tracks is allowed to vary through time, is considered in the last two papers. See Assad [1], Assad [2], Choe et al. [16], and Cordeau et al. [17] for a general review of rail transportation problems. However, because the rail classification problem considers inherent differences between the rail classification problem and the constrained sequencing problem, all sorting strategies discussed in the above cited papers are unrealistic to apply to the constrained sequencing problem (either with a diverging junction only, or with a random-access off-line buffer only) that are modeled in this dissertation.

 Another decision-making problem can be found in the Order Accumulation / Sortation System (OAS) in a typical automated distribution center. In a common order picking system design, the sortation functions are separated from the order picking functions. To retrieve the items of an order from the warehouse, picking systems are used and many of these systems use ‘pick-wave’ where a group of orders is picked simultaneously with each picker being responsible for picking a single group of items for all the orders in a wave. Such a wave approach has been found to be more efficient than a serial picking scheme (where each picker selects all the items for one or more orders) in many systems. However, wave picking requires further sorting that is not required by serial picking systems. After retrieval by the sorting system from the warehouse, items move as a wave to OAS where they are assigned to one of shipping lanes for sortation into orders. Assignments are made based on the adopted lane as-signment strategy and if recirculation is allowed, an item re-circulates OAS until a shipping lane is assigned to that item. Therefore, identifying the optimal lane assignment strategy can be considered as a special case of the constrained se-quencing problem with a diverging junction and an off-line buffer (i.e. recirculating conveyor) as in <Figure 4>.

<Figure 4> Lane Assignment Problem as a Special Case of the Constrained Sequencing Problem

 However, like the rail classification problem, the lane as-signment problem in OAS has a few characteristics different from the constrained sequencing problem as follows. First, capacity of each shipping lane needs to be explicitly con-sidered. Second, an order may be pre-assigned to a specific shipping lane (e.g. a shipping lane dedicated for FedEx). Finally, if an order is not pre-assigned, usually a nonempty lane is dedicated to an order until the lane receives all items of that order. As a result, there are two common categories of lane assignment strategies-fixed priority rules and the next available rules (i.e. incidental rules). Fixed priority rules include such popular rules as ‘sort the largest (or smallest) orders first’ while the next available rules assign the next available lane to the item belonging to an order that has not yet been assigned any lane.

 Research on OAS is relatively scarce even though there exist many implementations of such systems in industry (see Johnson and Lofgren [28], Gould [22], Gould [23], Horrey  [26], Schwind [41], and Witt [46]). In one of the first papers to analyze OAS, Bozer and Sharp [9] used simulation to eval-uate the throughput of OAS as a function of the number and length of lanes, the presence of a recirculation conveyor, the control system, and the induction capacity with the assump-tion that each lane is assigned to one order. Bozer et al. [8] also used simulation to examine various line assignment strat-egies as well as wave release strategies under the assumption that there are more orders than lanes in OAS, finding in-cidental rules consistently outperforms fixed priority rules. Johnson [27] proves this result by an analytical model for OAS. Choe [13], Choe and Sharp [14], Choe et al. [15], and Choe et al. [16] deal with questions on the design of both the picking system and its relationship to OAS. They developed approximate queueing models for the picking and OAS sub-systems and incorporated those models into an overall analy-sis of the effect of picking schemes. Meller [32] developed an algorithm for finding optimal lane assignment strategy when truck-loading requirements governs the sequence of or-der sortation. Customer orders are reverse loaded to company owned trucks with pre-specified delivery routes in the appro-priate sequence based on the truck’s route. A binary integer program is formulated and solved and this model assigns trucks and orders to shipping lanes with the objective of mini-mizing the total sorting time. Apart from the research specific to OAS, research on conveyor theory has been widely con-ducted (Muth [37] for a general review and Bastani [4] for recent works). However, all of those works deal with issues on material flow on the conveyor system (e.g. throughput, num-ber of loading/unloading stations, time delay, and capacity).

 Despite the fact that there is a large body of literature on sequencing assembly lines, most work adopts a static ap-proach as a basic assumption of the problem (see Baybars [5] and Yano and Bolat [48] for a general review) and does not consider the constraints imposed by the material handling de-vices, such as strict FIFO constraints on a conveyor. The pri-mary concern of a static approach is how to determine a sin-gle job sequence for the entire line for an available or recur-ring set of jobs, whereas the objective is, typically, to balance workload among the different processing departments (see Lee and Vairaktarakis [31] and Yano and Rachamadugu [49]). However, a dynamic approach would change the sequence on the fly for a given line without mechanical sequencing constraints.

 Few papers, especially those that deal with mixed assem-bly lines, consider sequence-dependent setups. For example, Burns and Daganzo [11] and Bolat et al. [7] consider lines where different jobs have different attributes or options and a setup occurs whenever two jobs with different options fol-low each other. They develop heuristics for sequencing these jobs with the objective of minimizing total setup cost.  However, they do not consider the issue of constrained se-quencing and assume that jobs have unique attributes. The issue of sequencing jobs with options is also discussed by Yano and Rachamadugu [49] that considers cases where jobs with different options have different processing times. However, they assume that there is no setup between jobs with different options.

 The issue of sequence-dependent setups has been addressed extensively in the traditional scheduling literature. Most such papers consider a single machine problem with multiple jobs, where individual jobs may belong to different families. A set-up occurs whenever two consecutive jobs belong to different families. The individual jobs, irrespective of family member-ship, may carry different weights and have different due dates. The objective is to determine a sequence of jobs that optimizes one or more performance measures- typically, a function of job completion time such as maximum lateness, weighted completion time, or weighted tardiness. Examples of this work include Monma and Potts [33], Potts and Wassenhove [40], Unal and Kiran [44], and Webster and Baker [45]. In general, scheduling with sequence-dependent setups is NP-hard, with polynomial algorithms available only for a few special cases (see Bruno and Downey [10] and Laporte [30]).

 In all of the above literature on scheduling, mixed assembly line, or sequence-dependent setups, it is assumed that there is full flexibility as to how jobs are sequenced-i.e. not con-strained by the sequence change mechanism. It is also as-sumed that setups are family-or lot-specific, with family or lot membership being known. The problem discussed in this paper is different from all those in above literature in two aspects. First, it is assumed that there is only constrained flexibility in how jobs can be re-sequenced. Second, some flexibility is allowed in assigning attributes that determine family membership among jobs.

3. Analytical Modeling

3.1 Constant Setup Cost with a Fixed Number of Downstream Queues

 The simplest diverging junction is a single upstream queue feeding Q identical downstream queues. The problem is to decide which job is sent to which downstream queue to mini-mize total setup cost on all downstream queues. We assume as follows :

 1. The number of downstream queues is fixed.

 2. Setup cost is independent of job attributes and downstream queues.

 3. The number of jobs in the upstream queue is fixed.

 4. The attributes of all jobs in the upstream queue are fixed.

 5. The capacity of each downstream queue is unlimited.

 6. There is no setup cost for the first and last jobs sent to each downstream queue.

 7. FIFO discipline is applied on all queues.

 8. All setups are done instantaneously-no setup time.

 Assumption 6 means that if all jobs in a downstream queue have identical attributes, then no setup cost is assumed for that queue. This assumption can be relaxed by adding con-straints that explicitly consider setup costs for the first and last jobs. Assumption 1 and 2 are relaxed in Section 3.2 as the model is extended. We also need to introduce the following notations :

 U = upstream queue

 Q = number of downstream queues

 N = number of jobs in U

 C = changeover cost, a constant for each changeover

 One can find the following properties of the constrained sequencing problem.

Property 1.1:Dispatching Constraint

 The FIFO discipline of U prohibits the i^th job in U from being dispatched before the (i-1)^thjob in U is dispatched.

Property 1.2:Conservation of Precedence Relationship

 Due to Property 1.1, the precedence relationship among jobs in U is maintained in each downstream queue. That is, if  the i^th job precedes the j^th job in U and both are dispatched to the same downstream queue, then the i^th job precedes the j^th job in the downstream queue.

 The above two properties restrict the range of x_ij so that index i is always less than j. In addition, if each job as well as each downstream queue is represented as a node in a network, then represent each feasible arc in this network can be associated with x_ij, y_jq, or z_qi. Furthermore, the defi-nitions of x_ij, y_jq, and z_qi require that each node has exactly one incoming arc and one outgoing arc. This way the con-strained sequencing problem can be transformed as a network problem. <Figure 5> shows a possible dispatching result from the example in <Figure 1>, where <Figure 6> is the associated network representation.

<Figure 5> A Possible Dispatching Result for the Example in <Figure 1>

<Figure 6> Network Representation Associated with <Figure 5>

 The network described above can be interpreted such that if a job is directly connected with another job by variable x, then these two jobs are sent to the same downstream queue and are adjacent to each other in that queue. For the first job sent to a downstream queue, the incoming arc to the associated node is represented by z. For the last job, the outgoing arc from the associated node is represented by y. In <Figure 6>, a downstream queue has jobs 1 and 4, and another downstream queue has jobs 2, 3, and 5, in sequence. Then as discussed in Han [25] and Han [24], the above net-work representation can be transformed into the following mixed-integer programming (MIP) formulation.

 subject to

 The objective function (1) is the total setup cost of all jobs after dispatching. The Property 1.1 and 1.2 are ensured by not defining variables x_ij if index i is equal to or bigger than j. (2) ensures that any job i is assigned a successor job among all jobs after the i^th job in U, or is assigned as the last job in a downstream queue. (3) ensures that any job j is assigned a predecessor job among all jobs preceding the i^th job in U, or is assigned as the first job in a down-stream queue. The intention of (4) and (5) is that each down-stream queue is assigned exactly one first job and one last job, respectively. Note that if the first job is the same as the last job, then only one job is assigned to that downstream queue. The unintended result of (4) and (5) is that each downstream queue is utilized - i.e. at least one job is assigned - even when it is not necessary. In reality, achieving the minimum setup cost may not require all Q  queues to be utilized. To find the minimum number of queues for achiev-ing the minimum cost, one may try to find an optimal sol-ution with Q, Q-1, Q-2 , … queues until the minimum cost starts to increase. Another possible way of simulta-neously identifying the number of queues to be used as well as the minimum cost is explained in Section 3.2.

 Constraint (6) is added because the meaning of the deci-sion variables demands integrality. However, (6) can be re-moved without loss of generality because of the following reasoning. A matrix is called totally unimodular if the deter-minant of every square submatrix formed from it has determi-nant -1, 0, or +1 (Bazaraa et al. [6]). If our MIP formulation is represented as ‘maximize c subject to Ax = b where b is a binary variables vector’, then A is a node-arc incidence matrix of a network because our formulation can be repre-sented as a network. Note that the node-arc matrix is com-posed of (0, 1, –1), has two no-zero entries in each column, and the summation of each column equals zero.

 In addition, if a matrix composed of (0, 1, –1) has no more than two no-zero entries in each column and the sum-mation of all elements in column j equals zero if column j contains two no-zero coefficients, then this matrix is totally unimodular (Nemhauser and Wolsey [39]). Therefore, A is totally unimodular because A is composed of (0, 1, –1), has two no-zero entries in each column, and the summation of each column equals zero. Furthermore, if A is totally un-imodular and each element of b is integer-valued, then the optimal solution assigns all variables integer values (see Shapiro [42] for a proof). Therefore, (6) can be removed. With (6) removed, the formulation reduces to the well-solved assignment problem. The removal of (6) without loss of gen-erality can also be proved by showing a one-to-one corre-spondence relationship between two equally sized sets com-posed of all jobs and queues as illustrated in <Figure 7>.

<Figure 7> Assignment Problem Example of 3 Jobs and 2 Queues

 Because the Hungarian method can solve the assignment problem optimally in O(N³), modeling it as an assignment problem - compared to modeling it as an MIP or LP problem - has advantages in terms of speed and implementation cost. For speed, practical problems can be solved with a few hun-dred jobs to optimality in several seconds, allowing for on-the-spot optimal control in many applications. For im-plementation cost, dispatching logic in diverging or converging junctions of conveyors is usually implemented by Programm-able Logic Controllers (PLCs). A PLC has limited memory, usually a few megabytes, and CPU power. Therefore, in most cases implementing an MIP- or LP-based algorithm in PLC environment requires an external system - where the MIP/LP solver is loaded - and a network module connecting the ex-ternal system and PLC, causing high hardware and software costs. In contrast, implementing an assignment-problem-based algorithm can save implementation time and cost since it can be implemented in a PLC standalone environment and is relatively easy to program and debug.

3.2 Attribute Dependent Setup Cost with a Variable Number of Downstream Queues

3.2.1 Introduction

 In reality, setup cost often depends on downstream queues and the attributes of the job to be processed. For example, the setup cost for color change in the paint shop usually depends on the paint color to be changed. In general, setup cost depends on both the job just finished and the job to be processed next. In addition, in the simple constrained se-quencing problem model discussed in section 3.1., each downstream queue is forced to have at least one job. In the conveyor system design stage, the number of downstream conveyors is a design parameter. The cost of an additional conveyor, processing station, and extra floor space can out-weigh the cost savings from setup reduction. In system oper-ation, utilizing each additional downstream queue and work-station may incur extra costs for the labor, energy, and initial process setup. At one extreme, if the number of downstream queues is equal to one, no re-sequencing is possible. At the other extreme, if the number of queues is equal to the number of attributes, no setup cost is necessary because each queue can have jobs with identical attributes. Therefore, for a given set of jobs and cost values, if R and K denote the optimum number of downstream queues and the number of attributes, respectively, then the following condition holds :  

 Based on (7), the maximum number of downstream queues one needs to consider is K. Each downstream queue is des-ignated to a specific attribute if K queues are available for use. However, when the queue installation cost is considered, the optimum number of downstream queues is a variable and is often less than K. The rationale here is to start with max-imum K, then to decide which queue to use and which queue not to use to minimize total cost. First, define the cost param-eters as follows :

 C′_ij = changeover cost when i^th  job in U is located

 right before the j^th job in U on a downstream queue (for the case that a specific attribute is given to each job in U and it is known in advance)

 C′_q = cost of installing downstream queue q

 Recall from Section 3.1., constraints (4~5) restrict each queue to exactly one incoming unit flow and one outgoing unit flow, shown in <Figure 8>.

<Figure 8> Part of the Network Representation for the Model in Section 3.1

 A side effect of these constraints is that each queue is assigned at least one job. In this Section, the number of queues to be constructed is an integer and some queues are allowed to have no assigned job. The challenge is to allow some queues have no assigned job and, at the same time, to maintain a node-arc model.

 Although there might be different ways of modeling such a situation, the approach taken here is to use all K queue nodes. Virtual arcs w_qj are defined to designate the outgoing flow from the unused queue node q to other queue node.  Similarly, virtual arcs w_iq are defined to designate the incom-ing flow to queue node q-q may or may not be used- to go from other queue node. The extended queue node in this definition is depicted in <Figure 9>.

<Figure 9> Extension the Network Representation in <Figure 7>

 For each queue node, constraints

 are added. The former restricts a queue to have an entering arc either from a job, or from another queue. The latter sim-ilarly restricts the exiting arc. With the addition of virtual arcs and the above two constraints, a node-arc model can be built for the problem.

3.2.2 Installation Cost Calculation

 The fact that no job is assigned to a queue with virtual links complicates the calculation for installation cost. Furth-ermore, a queue with or without an assigned job may be connected with other queues via virtual arcs. One way to handle this is to assign half of the installation cost to each arc connecting a job and a queue.

 In this way, if queue q is connected from a job and con-nects to a job, the total cost becomes correct. If queue q is connected from queue i (q ≠ i) and connects to a job, an adjustment need to be made by associating cost  to virtual arc w_iq. This treatment makes up the installation cost for queue q () which can-cels out the installation cost for queue i ().

 Before the other cases are explained, the auxiliary in-stallation cost associated with queue q, denoted as AC_q, is defined. AC_q represents the summation of costs of the arcs that start from or end at queue q. Then AC_q is defined as follows :

 Note that terms

 are divided by 2 because these terms are double-counted when AC_q is summed for all queues for use in the MIP formulation. Since queues are interconnected by variable w, AC_q inevitably takes the following recursive form :

 AC_q = true installation cost of queue q+f(w_iq, AC_i)+f(w_qj, ACj), where f() denotes a function.

 It will be shown that all f(w_iq, AC_i)and f(w_qj, AC_j) terms in the above equation eventually cancel out if one sums AC_q over all queues, resulting in AC_q = total queue in-stallation cost.

 First, from

 and all these variables are integers by definition. Therefore, each queue q can be classified into the following four cases based on all ossible combinations made by

 Case 1 :

 For Case 1,

 Because

 queue q is not connected with any other queue and it is clear that AC_q = the true installation cost of queue q = C_q^〃 . <Figure 6> shows an example for case 1. This example- as well as other examples corresponding to other cases-is one of the possible dispatching results from the situation explained in <Figure 1>, without an off-line buffer. In <Figure 9>,
AC_q = C_q^〃 and AC_q = C_a^〃+C_b^〃
which represents the total queue installation cost correctly.

 Case 2 :

 For case 2,

 Because

 there is only one queue, denoted r, connected with queue q and queue r belongs to either case 3 or case 4.

 Therefore,

 If queue r belongs to case 3, there is only one queue, q, that is connected with queue r and AC_q + AC_r = C_r^〃 by (8). If queue r belongs to case 4, queue r is connected with a queue belonging either to case 2 or case 4. The sub-network of the associated problem network, composed of queues in-cluding q and r and arcs connecting these queues takes form by sequentially connecting one queue in case 2, some queues in case 4, and one queue in case 3; the number of queues in case 4 ranges from zero to Q-2. By using (8~10), one can get AC_b = C_r^〃, where b∈set of all queues in this sub-network. If this sub-network is interpreted such that queue q is used and all other queues in the sub-network are not used, AC for each queue in this sub-network represents queue installation cost correctly. An illustrative example of case 2 is shown in <Figure 10>, where AC_q + AC_r = C_r^〃; queue p is in case 3.

<Figure 10> Example of Case 2

 Case 3 :

 For case 3,

 Because

there is only one queue, p, connected with queue q and queue p belongs to either case 2 or case 4.

 Therefore,

 If queue p belongs to case 2, there is only one queue, q, that is connected with queue p and AC_q + AC_p = C_p^〃 by (9). If queue p belongs to case 4,it is connected with a queue belonging either to case 3 or case 4. The sub-network com-posed of queues that include q and p and arcs connecting these queues takes form by sequentially connecting one queue in case 3, some queues in case 4, and one queue in Case 2; the number of queues in case 4 ranges from zero to Q-2. By using (8~10), one can get AC_b = C_r^〃. where b∈ set of all queues in this sub-network. If this sub-network is interpreted such that queue q is used and all other queues in this sub-network are not used, then AC for each queue in this sub-network represents the queue installation cost correctly. <Figure 11> shows an example of case 3 where AC_q + AC_r = C_r^〃; queue p is in case 2.

<Figure 11> Example of Case 3

 Case 4 :

 For Case 4,

 Because

 queue q is connected from a queue, s, belonging to case 2 or case 4 and is connected to a queue, t, belonging to case 3 or case 4.

 Therefore,

 Using similar reasoning to that for case 2 and case 3, one can think of a sub-network composed of queues including q and s, and t and arcs connecting these queues. In addition, one can conclude that AC for each queue in this sub-network represents the queue installation cost correctly. An example of case 4 is shown in <Figure 12> where AC_q+AC_s+AC_t = C_t^〃; queue s is in case 2 and queue t is in case 3.

<Figure 12> Example of Case 4

 Summarizing the discussions in the above four cases, the following facts can be derived :

 · f(w_iq, AC_i) and f(w_jq, AC_j) will eventually cancel out to zero if one sums up AC_q over all queues, resulting in AC_q= total queue installation cost.

 · w_qi = 1 means that queue q is a queue with no as-signed job, and w_qj = 0 means that queue q is a queue with at least one job assigned.

 Note that if cost (not ) is associated with variable w_ij, then w_iq = 1 means that queue q is a queue with no assigned job, and w_iq = 0 means that queue q is a queue with at least one job assigned.

 Finally, one needs to calculate

3.2.3 Model Formulation

 Summarizing the discussion in section Ⅲ, a MIP model that explicitly considers the number of available queues and the attribute-dependent setup cost can be formulated as follows :

 subject to

 The first term in the objective function is the sum of the setup cost of all jobs in all downstream queues, as in the simple model in Section 3.1, while the second term is the cost of adding queue q and the third term is for canceling the cost correction due to over accounting in the second term. We also note that the objective function can be simplified as follows :

 Explanations for constraints (11~12) are given in Section 3.1. For (13~15), newly added variables w are needed to identi-fy unused queues. Again, (15) can be safely removed using the same reasoning as in Section 3.1-total unimodularity. As a result, the problem again becomes the well-solved assign-ment problem. Note that it is meaningless to differentiate the cost of installing downstream queues from the cost of using downstream queues. Differentiating these two costs is mean-ingful only when it is possible to have a downstream queue that is not used in dispatching, which is not the case in our model-for any solution having an unused downstream queue, an equal or better solution having no unused downstream queue can be found. As a simple proof, for any solution having an unused queue, think of the modified solution with one job as-signed to the unused queue. Because of the assumption that there is no setup cost for the first job assigned to a downstream queue, the modified solution has an equal or lesser total setup cost, depending whether or not the predecessor job and the successor job of the assigned job have the same attributes.

4. Contributions and Future Directions

 In this paper, analytical models have been developed for a constrained sequencing problem with a diverging junction. We also modeled cases where the number of downstream queues needs to be decided simultaneously as well as cases where setup cost depends on both the job just finished and the job to be processed next. It has been proved that problems with practical size such as several hundred jobs can be solved quickly by these models.

 Even though this paper did extensive analysis of diverging junction cases, no analysis has been made of off-line buffer cases, converging junction cases, and off-line buffer cases. If making an optimization model for these cases can be done successfully, a whole conveyor system can be analyzed sys-tematically by dividing the system into each diverging or converging junction and applying the appropriate model to each junction. This way heuristics can be devised to obtain a feasible solution for the whole system and the performance of the heuristics may be good because the solution is com-posed of local optimal solutions for each junction point.

 Future research also needs to seek to incorporate other constraints such as those on cycle time limitations into the models. In the interview we conducted with the paint shop plant managers, reducing the number of color changeovers (i.e. increasing average color block size) was usually not on the highest priority in making production decisions. In other words, the solution optimized only for reducing the number of changeovers is very likely to be declined on implemen-tation stage because performance of other criteria (that are considered more important than the number of changeovers) would be degraded greatly.

 Finally, using diverging or converging junction alone may not be the best solution for all cases requiring re-sequencing, especially when full re-sequencing capability is desired. In fact, many manufacturing facilities use AS/RS or selectivity bank for re-sequencing purpose. However, since it is believed that the approach of using junctions for re-sequencing is al-most always beneficial even with the existence of AS/RS or selectivity bank, the following two functionalities need to be included in the analytical models model discussed in this research :

 · Optimal capacity of AS/RS or selectivity bank in facility design phase needs to be decided. Since AS/RS or selec-tivity bank is expensive, minimizing its capacity is desired and use of junctions can greatly contribute to reducing re-quired capacity while meeting re-sequencing requirements.

 · Optimal dispatching decision needs to be made on all di-verging/converging conveyor junctions as well as on all diverging points (where jobs can go to AS/RS or to the next processing facility) and all converging points (where jobs can be received from AS/RS or from the previous processing facility).