Lập lịch các công việc giảm chất lượng để tối thiểu hóa thời gian hoàn thành trên một máy đơn

Chin-Chia Wu1, Yau-Ren Shiau2, Ling-Huei Lee1, Wen-Chiung Lee1
1Department of Statistics, Feng Chia University, Taichung, Taiwan
2Department of Industrial Engineering and System Management, Feng Chia University, Taichung, Taiwan

Tóm tắt

Các vấn đề lập lịch máy với các công việc giảm chất lượng đã thu hút sự chú ý ngày càng tăng trong những năm gần đây, chủ yếu tập trung vào các mô hình giảm chất lượng tuyến tính. Tuy nhiên, nếu một số quy trình bảo trì không hoàn thành trước thời hạn được chỉ định, các công việc sẽ cần thêm thời gian để hoàn thành thành công trong một số tình huống. Do đó, bài báo này đề cập đến một vấn đề máy đơn mà mục tiêu là tối thiểu hóa thời gian hoàn thành theo mô hình giảm chất lượng phân mảnh. Một thuật toán nhánh và giới hạn và hai thuật toán heuristic được cung cấp để tìm kiếm giải pháp tối ưu và các giải pháp gần tối ưu, tương ứng. Kết quả tính toán cũng được trình bày để đánh giá hiệu suất của các thuật toán được đề xuất.

Từ khóa

#lập lịch #công việc giảm chất lượng #thời gian hoàn thành #mô hình giảm chất lượng phân mảnh #thuật toán nhánh và giới hạn #thuật toán heuristic

Tài liệu tham khảo

Browne S, Yechiali U (1990) Scheduling deteriorating jobs on a single processor. Oper Res 38:495–498. doi:10.1287/opre.38.3.495 Kunnathur AS, Gupta SK (1990) Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem. Eur J Oper Res 47(1):56–64. doi:10.1016/0377-2217(90)90089-T Mosheiov G (1994) Scheduling jobs under simple linear deterioration. Comput Oper Res 21(6):653–659. doi:10.1016/0305-0548(94)90080-9 Cheng TCE, Ding Q (1998) The complexity of scheduling starting time dependent tasks with release times. Inf Process Lett 65(2):75–79. doi:10.1016/S0020-0190(97)00195-6 Wang JB, Xia ZQ (2005) Scheduling jobs under decreasing linear deterioration. Inf Process Lett 94:63–69. doi:10.1016/j.ipl.2004.12.018 Zhao CL, Tang HY (2005) Single machine scheduling problems with deteriorating jobs. Appl Math Comput 161:865–874. doi:10.1016/j.amc.2003.12.073 Lee WC, Wu CC, Liu HC (2009) A note on single-machine makespan problem with general deteriorating function. Int J Adv Manuf Technol. doi:10.1007/s00170-008-1421-9 Shiau YR, Lee WC, Wu CC, Chang CM (2007) Two-machine flowshop scheduling to minimize mean flow time under simple linear deterioration. Int J Adv Manuf Technol 34:774–782. doi:10.1007/s00170-006-0646-8 Toksari MD, Güner E (2008) Minimizing the earliness/tardiness costs on parallel machine with learning effects and deteriorating jobs: a mixed nonlinear integer programming approach. Int J Adv Manuf Technol 38:801–808. doi:10.1007/s00170-007-1128-3 Wang JB, Lin L, Shan F (2008) Single-machine group scheduling problems with deteriorating jobs. Int J Adv Manuf Technol 39:808–812. doi:10.1007/s00170-007-1255-x Kubiak W, van de Velde S (1998) Scheduling deteriorating jobs to minimize makespan. Nav Res Logistics 45:511–523. doi:10.1002/(SICI)1520-6750(199808)45:5<511::AID-NAV5>3.0.CO;2-6 Cheng TCE, Ding Q (2001) Single-machine scheduling with step-deteriorating processing times. Eur J Oper Res 134:623–630. doi:10.1016/S0377-2217(00)00284-8 Alidaee B, Womer NK (1999) Scheduling with time dependent processing times: review and extensions. J Oper Res Soc 50:711–720 Cheng TCE, Ding Q, Lin BMT (2004) A concise survey of scheduling with time-dependent processing times. Eur J Oper Res 152:1–13. doi:10.1016/S0377-2217(02)00909-8 Lee WC (2004) A note on deteriorating jobs and learning in single-machine scheduling problems. Int J Bus Econ 3:83–89 Wang JB, Cheng TCE (2007) Scheduling problems with the effects of deterioration and learning. Asia-Pacific J Oper Res 24(2):245–261. doi:10.1142/S021759590700122X Wang JB (2006) A note on scheduling problems with learning effect and deteriorating jobs. Int J Syst Sci 37(2):827–833. doi:10.1080/00207720600879260 Wang JB (2007) Single-machine scheduling problems with the effects of learning and deterioration. Omega 35:397–402. doi:10.1016/j.omega.2005.07.008 Wang X, Cheng TCE (2007) Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan. Eur J Oper Res 178:57–70. doi:10.1016/j.ejor.2006.01.017 Wang JB, Gao WJ, Wang LY, Wang D (2009) Single machine group scheduling with general linear deterioration to minimize the makespan. Int J Adv Manuf Technol. doi:10.1007/s00170-008-1667-2 Eren T, Güner E (2009) A bicriteria parallel machine scheduling with a learning effect. Int J Adv Manuf Technol. doi:10.1007/s00170-008-1436-2 Wu CC, Lee WC (2007) A note on single-machine scheduling with learning effect and an availability constraint. Int J Adv Manuf Technol 33:540–544. doi:10.1007/s00170-006-0469-7 Cai JY, Cai P, Zhu Y (1998) On a scheduling problem of time deteriorating jobs. J Complex 14:190–209. doi:10.1006/jcom.1998.0473 Panwalkar SS, Smith ML, Seidmann A (1982) Common due date assignment to minimize total penalty for the one machine scheduling problem. Oper Res 30(2):391–399. doi:10.1287/opre.30.2.391 Kirkpatrick S, Gelatt C, Vecchi M (1983) Optimization by simulated annealing. Science 220(4598):671–680. doi:10.1126/science.220.4598.671 Ben-Arieh D, Maimon O (1992) Annealing method for PCB assembly scheduling on two sequential machines. Int J Comput Integr Manuf 5(6):361–367. doi:10.1080/09511929208944543