Flow-shop scheduling with setup and assembly operations. (English) Zbl 1137.90534
Summary: A scheduling model for a production system including machining, setup and assembly operations is considered. Production of a number of single-item products is ordered. Each product is made by assembling a set of several different parts. First, the parts are manufactured in a flow-shop consisting of multiple machines. Then, they are assembled into products on a single assembly stage. Setup operation and setup time are needed when a machine starts processing the parts or it changes items. The operations are partitioned into several blocks. Each block consists of the machining operations, the setup operations, and the assembly operation(s) for one or several products. The parts of the same item in a block are processed successively. The objective function is the mean completion time for all products. We consider a problem to partition the operations into blocks and sequence the parts in each block so as to minimize the objective function. Solution procedures using pseudo-dynamic programming and a branch-and-bound method are proposed. Computational experiments are carried out to evaluate the performance of the solution procedures. It has been found that a good near-optimal schedule is obtained efficiently by the proposed solution procedures.
Keywords:
flow-shop scheduling; machining operation; assembly operation; setup time; block size; branch-and-bound; pseudo-dynamic programmingReferences:
| [1] | A. Allahverdi, C.T. Ng, T.C.E. Cheng, M.Y. Kovalyov, A survey of scheduling problems with setup times and costs, European Journal of Operational Research, in press, doi:10.1016/j.ejor.2006.06.060; A. Allahverdi, C.T. Ng, T.C.E. Cheng, M.Y. Kovalyov, A survey of scheduling problems with setup times and costs, European Journal of Operational Research, in press, doi:10.1016/j.ejor.2006.06.060 · Zbl 1137.90474 |
| [2] | Cheng, T. C.E., Analysis of material flow in a job shop with assembly operations, International Journal of Production Research, 28, 7, 1369-1383 (1990) |
| [3] | Cheng, T. C.E.; Wang, G., Scheduling the fabrication and assembly of components in a two-machine flow shop, IIE Transactions, 31, 2, 135-143 (1999) |
| [4] | Doctor, S. R.; Cavalier, T. M.; Egbelu, P. J., Scheduling for machining and assembly in a job-shop environment, International Journal of Production Research, 31, 6, 1275-1297 (1993) |
| [5] | French, S., Sequencing and Scheduling, An Introduction to Mathematics of the Job Shop (1982), Ellis Horwood Ltd.: Ellis Horwood Ltd. England · Zbl 0479.90037 |
| [6] | Fry, T. D.; Oliff, M. D.; Minor, E. D.; Leong, G. K., The effect of product structure and sequencing rule on assembly shop performance, International Journal of Production Research, 27, 4, 671-686 (1989) |
| [7] | Gaafar, L. K.; Masoud, S. A., Genetic algorithms and simulated annealing for scheduling in agile manufacturing, International Journal of Production Research, 43, 14, 3069-3085 (2005) · Zbl 1151.90407 |
| [8] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039 |
| [9] | Hariri, A. M.A.; Potts, C. N., A branch and bound algorithm for the two-stage assembly scheduling problem, European Journal of Operational Research, 103, 3, 547-556 (1997) · Zbl 0921.90091 |
| [10] | Huan, P. Y., A comparative study of priority dispatching rules in a hybrid assembly/job shop, International Journal of Production Research, 22, 3, 375-387 (1984) |
| [11] | Lee, C. Y.; Cheng, T. C.E.; Lin, B. M.T., Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem, Management Science, 39, 5, 616-625 (1993) · Zbl 0783.90054 |
| [12] | Lin, B. M.T.; Cheng, T. C.E., Fabrication and assembly scheduling in a two-machine flowshop, IIE Transactions, 34, 11, 1015-1020 (2002) |
| [13] | McKoy, D. H.C.; Egbelu, P. J., Minimizing production flow time in a process and assembly job shop, International Journal of Production Research, 36, 8, 2315-2332 (1998) · Zbl 0945.90563 |
| [14] | Philipoon, P. R.; Russel, R. S.; Fry, T. D., A preliminary investigation of multi-attribute based sequencing rules for assembly shops, International Journal of Production Research, 29, 4, 739-753 (1991) |
| [15] | Potts, C. N.; Sevast’janov, S. V.; Strusevich, V. A.; Wassenhove, L. N.V.; Zwaneveld, C. M., The two-stage assembly scheduling problem: Complexity and approximation, Operations Research, 43, 2, 346-355 (1995) · Zbl 0837.90069 |
| [16] | Rinnooy Kan, A. H.G., Machine Scheduling Problems (1976), Martinus Nijhoff: Martinus Nijhoff Hague · Zbl 0366.90092 |
| [17] | Thiagarajan, S.; Rajendran, C., Scheduling in dynamic assembly job-shops with jobs having different holding and tardiness costs, International Journal of Production Research, 41, 18, 4453-4486 (2003) · Zbl 1069.90047 |
| [18] | Thiagarajan, S.; Rajendran, C., Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness, weighted tardiness and weighted flowtime of jobs, Computers and Industrial Engineering, 49, 4, 463-503 (2005) |
| [19] | Yokoyama, M., Hybrid flow-shop scheduling with assembly operations, International Journal of Production Economics, 73, 2, 103-116 (2001) |
| [20] | Yokoyama, M.; Santos, D. L., Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times, European Journal of Operational Research, 161, 3, 754-770 (2005) · Zbl 1071.90022 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
