Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Lập lịch dòng sản phẩm với vận chuyển công việc giữa các giai đoạn
Tóm tắt
Có nhiều vấn đề lập lịch sản xuất và vận chuyển công việc chung phát sinh trong các hệ thống sản xuất hiện đại. Trong bài báo này, chúng tôi nghiên cứu hai vấn đề như vậy xuất hiện trong môi trường dòng sản phẩm, nơi có hai giai đoạn chế biến và một phương tiện vận chuyển duy nhất có sẵn để chuyển giao công việc hoàn thành từ giai đoạn đầu tiên sang giai đoạn thứ hai. Trong vấn đề đầu tiên, có một máy đơn trong mỗi giai đoạn của dòng sản phẩm và các công việc có kích thước khác nhau khi được tải lên phương tiện vận chuyển. Trong vấn đề thứ hai, có hai máy song song ở giai đoạn đầu và một máy đơn ở giai đoạn thứ hai, và phương tiện vận chuyển chỉ có thể chở một công việc trong mỗi chuyến hàng. Mục tiêu của cả hai vấn đề là tối thiểu hóa thời gian hoàn thành (makespan), tức là thời gian hoàn thành của công việc cuối cùng trong giai đoạn thứ hai. Cả hai vấn đề đều có độ phức tạp NP-khó rất cao. Đối với mỗi vấn đề, chúng tôi đề xuất một thuật toán heuristic nhanh và cho thấy rằng thuật toán heuristic có giới hạn tồi tệ nhất chặt chẽ là 2.
Từ khóa
#lập lịch #dòng sản phẩm #vận chuyển công việc #tối thiểu hóa thời gian hoàn thành #NP-hardTài liệu tham khảo
Chen, B. (1995). Analysis of classes of heuristics for scheduling two-stage flow shop with parallel machines at one stage. Journal of the Operational Research Society, 46, 234–244.
Chen, Z.-L. (2010). Integrated production and outbound distribution scheduling: Review and extensions. Operations Research, 58, 130–148.
Dósa, G. (2007). The tight bound of first fit decreasing bin-packing algorithm is \(\text{ FFD(I) } \le 11/9\text{ OPT(I) } + 6/9\). Lecture Notes of Computer Science, 4614, 1–11.
Gong, H., & Tang, L. (2011). Two-machine flowshop scheduling with intermediate transportation under job physical space consideration. Computers & Operations Research, 38, 1267–1274.
Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. The Bell System Technical Journal, 45, 1563–1581.
Gupta, J. N. D. (1988). Two-stage, hybrid flowshop scheduling problem. Journal of the Operational Research Society, 39, 359–364.
Gupta, J. N. D., & Tunc, E. A. (1991). Schedules for a two-stage hybrid flowshop with parallel machines at the second stage. International Journal of Production Research, 29, 1489–1502.
Hoogeveen, J. A., Lenstra, J. K., & Veltman, B. (1996). Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. European Journal of Operational Research, 1, 172–175.
Hurink, J., & Knust, S. (2001). Makespan minimization for flow-shop problems with transportation times and a single robot. Discrete Applied Mathematics, 112, 199–216.
Johnson, S. M. (1954). Optimal two- and three-machine production schedules with setup times included. Naval Research Logistics, 1, 61–68.
Karuno, Y., & Nagamochi, H. (2003). A better approximation for the two-machine flowshop scheduling problem with time lags. 14th annual international symposium on algorithms and computation (pp. 309–318). Kyoto, Japan.
Langston, M.-A. (1987). Interstage transportation planning in the deterministic flow-shop environment. Operations Research, 35, 556–564.
Lee, C. Y., & Chen, Z.-L. (2001). Machine scheduling with transportation considerations. Journal of Scheduling, 4, 3–24.
Lee, C. Y., & Strusevich, V. A. (2005). Two-machine shop scheduling with an uncapacited interstage transporter. IIE Transaction, 37, 725–736.
Lee, C. Y., & Vairaktarakis, G. L. (1998). Performance comparision of some classes of flexible flow shops and job shops. International Journal of Flexible Manufacturing Systems, 10, 379–405.
Maggu, P. L., & Das, G. (1980). On \(2\times n\) sequencing problem with transportaion times of jobs. Pure and Applied Mathematika Sciences, 12, 1–6.
Mendoza, A., Ventura, J., & Huang, K.-L. (2010). A flowshop scheduling problem with transportation times and capacity constraints. 11th international material handling research colloquium (pp. 296–304).
Naderi, B., Zandieh, M., & Shirazi, M. A. H. A. (2009). Modeling and scheduling a case of flexible flowshops: Total weighted tardiness minimization. Computers & Industrial Engineering, 57, 1258–1267.
Oğuz, C., Ercan, M. F., Cheng, T. E. C., & Fung, Y. F. (2003). Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop. European Journal of Operational Research, 149, 390–403.
Oulamara, A., & Soukhal, A. (2001). Flow shop scheduling problems with transportation and capacity constraints. IEEE International Conference on Systems, Man, and Cybernetics, 4, 2540–2545.
Panwalker, S. (1991). Scheduling of a two-machine flow shop with travel time between machines. Journal of the operational Research Society, 42, 609–613.
Ruiz, R., & Vázquez-Rodríguez, J. A. (2010). The hybrid flow shop scheduling problem. European Journal of Operational Research, 205, 1–18.
Sriskandarajah, C., & Sethi, S. P. (1989). Scheduling algorithms for flexible flowshops: Worst and average case performance. European Journal of Operational Research, 43, 143–160.
Stern, H. I., & Vitner, G. (1990). Scheduling parts in a combined production-transportation work cell. Journal of the Operational Research Society, 41, 625–632.
Tang, L., & Liu, P. (2009). Flowshop scheduling problems with transportation or deterioration between the batching and single machines. Computers & Industrial Engineering, 56, 1289–1295.
Veltman, B. (1993). Multiprocessor scheduling with communicaiton Delays. PhD Thesis, CWI, Amsterdam, The Netherlands.
Xuan, H., & Tang, L. (2007). Scheduling a hybrid flowshop with batch production at the last stage. Computers & Operations Research, 34, 2718–2733.
Yu, W., Hoogeven, J. A., & Lenstra, J. K. (2005). Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard. Journal of Scheduling, 7, 333–348.