|
...assembly, either assemblies individual parts, or assemblies of subassemblies. This product structure is typically represented as a multi-level assembly tree. In the combined part and assembly scheduling environment, the problem is considerably more challenging than that of a typical job shop scheduling problem. Scheduling of the final product involves scheduling and synchronization of the operations of the various components and assemblies. It is this joint consideration that increases the complexity of this scheduling problem when compared to the general job shop scheduling problem.
In this work an auction-based algorithm for simultaneous scheduling of all manufactured and assembled jobs in a dynamic environment is developed, where the objective function is to minimize both the due date penalties associated with the final products and the inventory cost of the work in process. To ensure scalability of the algorithm, it is totally distributed: the jobs and the manufacturing and assembly resources act as independent entities in the system in that they have their own local objectives and do not have any direct information about the other entities. The jobs compete for the time periods to be processed so that they minimize their due date and Work In Process (WIP) costs. The resources (we will use the term "machines" for simplicity for all manufacturing and assembly resources) adjust the prices of the time periods to maximize their profit. We use a Mixed-Integer Linear Programming (MILP) model to construct and evaluate the bids so that the auction mechanism mimics a Lagrangian-relaxation-based subgradient optimization thus ensuring its global optimality. The inner structure of the problem enables very efficient calculation of bids for each job or assembly. The auction-based algorithm is much better than the popular dispatching rules and more scalable than the MILP model or direct implementations of the subgradient algorithm.
The paper is organized as follows. The next section presents a description of the problem followed by a literature review of relevant areas. A formal mathematical programming formulation, the auction-theoretic framework, auction mechanism, and efficient shortest path solution of the job agent problem are described in Section 3. The proposed algorithm for dynamic scheduling of production-assembly networks is developed in Section 4. Section 5 presents an illustrated example, and a full factorial experimental design for evaluating the proposed approach is presented in Section 6. Finally, Section 7 presents a summary and conclusions.
2. Scheduling of production-assembly systems
The paper focuses on scheduling a generic dynamic production-assembly network including: (i) multiple final products; (ii) multiple production, subassembly and assembly layers; (iii) job shop or flow shop configuration for each layer; (iv) workstations with identical ("parallel") machines; (v) multiple required resources, e.g., operator and machine; (vi) dynamic arrival of orders/raw material; and (vii) different objective functions. Each final product consists of multiple items which can be individual parts or subassemblies. For the sake of consistency with the scheduling literature, each part and assembly is henceforth referred to as a job and each resource is referred to as a machine. A process plan associated with each job describes the operation sequence and the machines required for each operation. Each final job has an assigned due date, and the associated objective function is a due date and/or completion-time-based measure (e.g., tardiness, squared deviation, lateness, makespan, etc.). In addition, a holding cost penalizes the early production of the assembled components and represents the WIP cost. The model allows for a very flexible structure of holding costs: it can depend on the current stage in a job's production or assembly, time period, time period from starting the job's production or assembly (e.g., for perishable goods), etc.
Relative to the large body of scheduling literature, the scheduling of production-assembly networks is almost unexplored, especially in dynamic job shop environments. Cheng (1990) used a critical path approach in an analytical approximation of the mean and standard deviation of the job flow time in a dynamic job shop with assembly operations. However, the goal was to estimate but not optimize the flow time of the jobs. Lee et al. (1993), Potts et al. (1995) and Hariri and Potts (1997) studied makespan minimization in a static two-stage assembly flow shop scheduling problem. A branch-and-bound algorithm and heuristics for two machines at the first stage and one assembly machine at the second stage was suggested in Lee et al. (1993) whereas in Potts et al. (1995) and Hariri and Potts (1997) m machines at the first stage and one assembly machine at the second stage are suggested. Potts et al. (1995) developed heuristic algorithms and provide a worst-case analysis by formulating vector summing problems. Hariri and Potts (1997) suggested a branch-and-bound algorithm for the problem presented in Potts et al. (1995). Doctor et al. (1993) developed a heuristic algorithm to maximize machine utilization, subject to due date constraints in a static make-to-order job shop with up to three levels of assembly operations (assembly, subassembly and production levels). McKoy and Egbelu (1998) developed a MILP model to minimize the makespan. They also considered a static make-to-order job shop environment with machining and assembly operations and suggested a heuristic to reduce the computational time. Yokoyama (2001) used a two-phase branch-and-bound technique to minimize the weighted sum of the completion times for products in a static flow shop with one assembly station.
Hoitimt et al. (1990), Hoitimt et al. (1993), Czerwinski and Luh (1994), and Kaskavelis and Caramanis (1997) applied Lagrangian relaxation to the problem of the static scheduling of large-scale systems. Hoitimt et al. (1993) and Kaskavelis and Caramanis (1997) investigated the relaxation of capacity constraints in job shops whereas Hoitimt et al. (1990) and Czerwinski and Luh (1994) applied Lagrangian relaxation to all constraints in simple production-assembly networks. Kaskavelis and Caramanis minimized a weighted sum of completion times and holding cost. Hoitimt et al. (1990) and Hoitimt et al. (1993) studied the minimization of the weighted squared tardiness, and Czerwinski and Luh (1994) studied minimization of the sum of squared earliness and tardiness.
There is a large body of literature on dynamic scheduling in job shops and flexible manufacturing systems (see, e.g., Wu and Wysk (1989), Ishii and Talavage (1991), Shaw et al. (1992), Cho and Wysk (1993), Kim and Kim (1994), Jeong and Kim (1998), Kim et al. (1998), Arzi and Iaroslavitz (1999), Aydin and Oztemel (2000) and Raheja and Subramaniam (2002) and Shnits et al. (2004)) but it does not address assembly operations. Most of the published literature suggest the use of adaptive or learning algorithms to choose an appropriate dispatching rule based on the work floor status. The use of genetic algorithms for dynamic scheduling has been suggested by Mesghouni et al. (1999), Qi et al. (2000), Rossi and Dini (2000) and Chryssolouris and Subramaniam (2001). The genetic algorithms find a completely new schedule every time new information becomes available.
More recent approaches using distributed solution methodology have shown promising results while providing the added benefit of distributed control. Kutanoglu and Wu (1999), Dewan and Joshi (2000, 2002) and Wellman et al. (2001) have demonstrated the use of market mechanisms to determine prices derived through distributing bidding protocols to determine schedules under various WIP and due-date-based objective functions. When a subgradient scheme is applied to update the prices, these methods are close to the Lagrangian relaxation techniques mentioned above but they allow distributed dynamic scheduling. All these papers focus on the classical job shop scheduling problem. In Section 3.2 we describe an auction-theoretic approach and show its adaptation to production-assembly networks.
This paper extends the problem to provide a more comprehensive solution to the complete scheduling problem in a generic production-assembly dynamic environment with a wide variety of objective functions, yet maintaining the distributed nature of the solution that can handle any objective function associated with completion times, due dates and WIP....
NOTE: All illustrations and photos
have been removed from this article.
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.
|
