Optimal control strategies for single-machine family scheduling with sequence-dependent batch setup and controllable processing times. (English) Zbl 1328.90049
Summary: The problem of scheduling jobs on an unreliable single machine is considered in this paper. The scheduling problem is characterized by the following features: jobs are grouped into classes of equivalent jobs; the generalized due date model is adopted for each class of jobs; it is possible to reduce the processing time of a job, at the price of the payment of an extra cost; a costly setup is required when switching between jobs of different classes. The scheduling problem is solved from a perspective which is different from the traditional determination of an optimal sequence of jobs; in fact, the objective of the paper is to determine optimal control strategies (functions of the system state) which allow generating the optimal decisions during the evolution of the system, taking into account the actual system state. In this way, optimal decisions can be promptly taken also in the presence of perturbations which affect the single machine (such as breakdowns and slowdowns). To this aim, a specific optimal control problem is stated and solved in the paper.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 90C39 | Dynamic programming |
| 93C83 | Control/observation systems involving computers (process control, etc.) |
Keywords:
optimal control; family scheduling problems; sequence-dependent setup; controllable processing times; dynamic programmingReferences:
| [1] | Aicardi, M., Giglio, D., & Minciardi, R. (2007). Optimal strategies for real-time determination of the next job’s class in a single machine with setup times and controllable processing times. In Proceedings of the European control conference (pp. 3963-3968). |
| [2] | Aicardi, M., Giglio, D., & Minciardi, R. (2008). Optimal strategies for multiclass job scheduling on a single machine with controllable processing times. IEEE Transactions on Automatic Control, 53(2), 479-495. · Zbl 1367.90049 · doi:10.1109/TAC.2007.915166 |
| [3] | Akella, R., & Kumar, P. R. (1986). Optimal control of production rate in a failure prone manufacturing system. IEEE Transactions on Automatic Control, 31(2), 116-126. · Zbl 0579.90047 · doi:10.1109/TAC.1986.1104206 |
| [4] | Akturk, M., & Ilhan, T. (2011). Single cnc machine scheduling with controllable processing times to minimize total weighted tardiness. Computers & Operations Research, 38, 771-781. · Zbl 1202.90111 · doi:10.1016/j.cor.2010.09.004 |
| [5] | Allahverdi, A., Gupta, J. N. D., & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega, The International Journal of Management Science, 27, 219-239. · doi:10.1016/S0305-0483(98)00042-5 |
| [6] | Allahverdi, A., Ng, C. T., Cheng, T. C. E., & Kovalyov, M. Y. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187, 985-1032. · Zbl 1137.90474 · doi:10.1016/j.ejor.2006.06.060 |
| [7] | Aytug, H., Lawley, M. A., McKay, K., Mohan, S., & Uzsoy, R. (2005). Executing production schedules in the face of uncertainties: A review and some future directions. European Journal of Operational Research, 161(1), 86-110. · Zbl 1115.90025 · doi:10.1016/j.ejor.2003.08.027 |
| [8] | Cai, Y., Kutanoglu, E., Hasenbein, J., & Qin, J. (2012). Single-machine scheduling with advanced process control constraints. Journal of Scheduling, 15, 165-179. · Zbl 1280.90036 · doi:10.1007/s10951-010-0215-8 |
| [9] | Cheng, T., & Kovalyov, M. (1995). Single machine batch scheduling with deadlines and resource dependent processing times. Operations Research Letters, 17, 243-249. · Zbl 0858.90073 · doi:10.1016/0167-6377(95)00011-8 |
| [10] | Cheng, T., Janiak, A., & Kovalyov, M. (1998). Bicriterion single machine scheduling with resource dependent processing times. SIAM Journal on Optimization, 8(2), 617-630. · Zbl 0907.68113 · doi:10.1137/S1052623495288192 |
| [11] | Cheng, T., Janiak, A., & Kovalyov, M. (2001). Single machine batch scheduling with resource dependent setup and processing times. European Journal of Operational Research, 135, 177-183. · Zbl 1077.90525 · doi:10.1016/S0377-2217(00)00312-X |
| [12] | Daniels, R. (1990). A multi-objective approach to resource allocation in single machine scheduling. European Journal of Operational Research, 48(2), 226-241. · Zbl 0825.90535 · doi:10.1016/0377-2217(90)90376-M |
| [13] | Daniels, R., & Kouvelis, P. (1995). Robust scheduling to hedge against processing time uncertainty in single-stage production. Management Science, 41(2), 363-376. · Zbl 0832.90050 · doi:10.1287/mnsc.41.2.363 |
| [14] | Di Febbraro, A., Minciardi, R., & Sacone, S. (2002). Optimal control laws for lot-sizing and timing of jobs on a single production facility. IEEE Transactions on Automatic Control, 47(10), 1613-1623. · Zbl 1364.90153 · doi:10.1109/TAC.2002.803527 |
| [15] | Epstein, L., Levin, A., Marchetti-Spaccamela, A., Megow, N., Mestre, J., Skutella, M., & Stougie, L. (2010). Universal sequencing on a single machine. In Proceedings of the 14th international conference on integer programming and combinatorial optimization (pp 230-243). · Zbl 1285.90008 |
| [16] | Gavett, J. (1965). Three heuristic rules for sequencing jobs to a single production facility. Management Science, 11(8), B166-B176. · doi:10.1287/mnsc.11.8.B166 |
| [17] | Gazarik, M., & Wardi, Y. (1998). Optimal release times in a single server: An optimal control perspective. IEEE Transactions on Automatic Control, 43(7), 998-1002. · Zbl 0949.90021 · doi:10.1109/9.701110 |
| [18] | Giglio, D. (2015a). A MILP model for single machine family scheduling with sequence-dependent batch setup and controllable processing times. arXiv:1501.07396 [math.OC]. · Zbl 1328.90049 |
| [19] | Giglio, D. (2015b). Fundamental lemmas for the determination of optimal control strategies for a class of single machine family scheduling problems. arXiv:1502.00423 [math.OC]. · Zbl 1328.90049 |
| [20] | Giglio, D., & Minciardi, R. (2011). Multiclass job scheduling on a single machine: updating optimal control strategies when due-dates change in real-time. In Proceedings of the 50th IEEE conference on decision and control and European control conference (pp 7923-7930). |
| [21] | Gokbayrak, K., & Selvi, O. (2010). Service time optimization of mixed-line service time optimization of mixed-line flow shop systems. IEEE Transactions on Automatic Control, 55(2), 395-404. · Zbl 1368.90069 · doi:10.1109/TAC.2009.2037273 |
| [22] | Graham, R., Lawler, E., Lenstra, J., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287-326. · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [23] | Gupta, A., & Sivakumar, A. (2005). Multi-objective scheduling of two-job families on a single machine. Omega, 33, 399-405. · doi:10.1016/j.omega.2004.07.010 |
| [24] | Hall, N. G., Sethi, S. P., & Sriskandarajah, C. (1991). On the complexity of generalized due date scheduling problems. European Journal of Operational Research, 51(1), 100-109. · Zbl 0742.90043 · doi:10.1016/0377-2217(91)90149-P |
| [25] | Ivanov, D., & Sokolov, B. (2012). Dynamic supply chain scheduling. Journal of scheduling, 15(2), 201-216. · Zbl 1280.90051 · doi:10.1007/s10951-010-0189-6 |
| [26] | Janiak, A., Kovalyov, M., & Portmann, M. C. (2005). Single machine group scheduling with resource dependent setup and processing times. European Journal of Operational Research, 162(1), 112-121. · Zbl 1132.90325 · doi:10.1016/j.ejor.2002.11.004 |
| [27] | Jin, F., Gupta, J., Song, S., & Wu, C. (2010). Single machine scheduling with sequence-dependent family setups to minimize maximum lateness. Journal of the Operational Research Society, 61, 1181-1189. · Zbl 1193.90101 · doi:10.1057/jors.2009.63 |
| [28] | Kayvanfar, V., Mahdavi, I., & Komaki, G. (2013). Single machine scheduling with controllable processing times to minimize total tardiness and earliness. Computers & Industrial Engineering, 65, 166-175. · doi:10.1016/j.cie.2011.08.019 |
| [29] | Khmelnitsky, E., Kogan, K., & Maimon, O. Z. (1997). Maximum principle-based methods for production scheduling with partially sequence-dependent setups. International Journal of Production Research, 35(10), 2701-2712. · Zbl 0942.90548 · doi:10.1080/002075497194390 |
| [30] | Kimemia, J., & Gershwin, S. B. (1983). An algorithm for the computer control of a flexible manufacturing system. IEE Transactions, 15(4), 353-362. · doi:10.1080/05695558308974659 |
| [31] | Kolahan, F., & Liang, M. (1998). An adaptive ts approach to jit sequencing with variable processing times and sequence-dependent setups. European Journal of Operational Research, 109, 142-159. · Zbl 0951.90025 · doi:10.1016/S0377-2217(97)00098-2 |
| [32] | Leung, J. Y. T., & Pinedo, M. (2004). A note on scheduling parallel machines subject to breakdown and repair. Naval Research Logistics, 51(1), 60-71. · Zbl 1055.90035 · doi:10.1002/nav.10105 |
| [33] | Lu, C. C., Lin, S. W., & Ying, K. C. (2012). Robust scheduling on a single machine to minimize total flow time. Computers & Operations Research, 39, 1682-1691. · Zbl 1251.90167 · doi:10.1016/j.cor.2011.10.003 |
| [34] | Ma, Y., Chu, C., & Zuo, C. (2010). A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering, 58, 199-211. · doi:10.1016/j.cie.2009.04.014 |
| [35] | Maimon, O. Z., & Gershwin, S. B. (1988). Dynamic scheduling and routing for flexible manufacturing systems that have unreliable machines. Operations Research, 36(2), 279-292. · doi:10.1287/opre.36.2.279 |
| [36] | Mao, J., & Cassandras, C. (2007). Optimal control of two-stage discrete event systems with real-time constraints. Discrete Event Dynamic Systems, 17, 505-529. · Zbl 1126.49015 · doi:10.1007/s10626-007-0019-y |
| [37] | Monma, C., & Potts, C. (1989). On the complexity of scheduling with batch setup times. Operations Research, 37(5), 798-804. · Zbl 0686.90025 · doi:10.1287/opre.37.5.798 |
| [38] | Mor, B., & Mosheiov, G. (2014). Batch scheduling of identical jobs with controllable processing times. Computers & Operations Research, 41, 115-124. · Zbl 1348.90291 · doi:10.1016/j.cor.2013.08.007 |
| [39] | Ng, C., Cheng, T., & Kovalyov, M. (2003a). Batch scheduling with controllable setup and processing times to minimize total completion time. Journal of the Operational Research Society, 54, 499-506. · Zbl 1070.90044 · doi:10.1057/palgrave.jors.2601537 |
| [40] | Ng, C., Cheng, T., Kovalyov, M., & Lam, S. (2003b). Single machine scheduling with a variable common due date and resource-dependent processing times. Computers & Operations Research, 30(8), 1173-1185. · Zbl 1047.90022 · doi:10.1016/S0305-0548(02)00066-7 |
| [41] | Ng, C., Cheng, T., & Kovalyov, M. (2004). Single machine batch scheduling with jointly compressible setup and processing times. European Journal of Operational Research, 153, 211-219. · Zbl 1137.90512 · doi:10.1016/S0377-2217(02)00732-4 |
| [42] | Ng, C., Cheng, T., Janiak, A., & Kovalyov, M. (2005). Group scheduling with controllable setup and processing times: Minimizing total weighted completion time. Annals of Operations Research, 133, 163-174. · Zbl 1119.90020 · doi:10.1007/s10479-004-5030-1 |
| [43] | Nowicki, E., & Zdrzalka, S. (1990). A survey of results for sequencing problems with controllable processing times. Discrete Applied Mathematics, 26, 271-287. · Zbl 0693.90056 · doi:10.1016/0166-218X(90)90105-L |
| [44] | Ouelhadj, D., & Petrovic, S. (2009). A survey of dynamic scheduling in manufacturing systems. Journal of Scheduling, 12(4), 417-431. · Zbl 1185.90089 · doi:10.1007/s10951-008-0090-8 |
| [45] | Panwalkar, S., & Rajagopalan, R. (1992). Single-machine sequencing with controllable processing times. European Journal of Operational Research, 59(2), 298-302. · Zbl 0760.90058 · doi:10.1016/0377-2217(92)90144-X |
| [46] | Pepyne, D., & Cassandras, C. (1998). Modeling, analysis, and optimal control of a class of hybrid systems. Discrete Event Dynamic Systems: Theory and Applications, 8, 175-201. · Zbl 0915.93027 · doi:10.1023/A:1008237701804 |
| [47] | Perkins, J. R., & Kumar, P. R. (1989). Stable, distributed, real-time scheduling of flexible manufacturing/assembly/disassembly systems. IEEE Transactions on Automatic Control, 34(2), 139-148. · Zbl 0674.90041 · doi:10.1109/9.21085 |
| [48] | Pinedo, M. (1995). Scheduling. Theory, algorithms and systems. Englewood Cliffs: Prentice-Hall Inc. · Zbl 1145.90393 |
| [49] | Potts, C., & Kovalyov, M. (2000). Scheduling with batching: A review. European Journal of Operational Research, 120, 228-249. · Zbl 0953.90028 · doi:10.1016/S0377-2217(99)00153-8 |
| [50] | Presby, J., & Wolfson, M. (1967). An algorithm for solving job sequencing problems. Management Science, 13(8), B454-B464. · doi:10.1287/mnsc.13.8.B454 |
| [51] | Qi, X., Yu, G., & Bard, J. F. (2002). Single machine scheduling with assignable due dates. Discrete Applied Mathematics, 122, 211-233. · Zbl 1019.90024 · doi:10.1016/S0166-218X(01)00316-X |
| [52] | Raman, N., Rachamadugu, R., & Talbot, F. (1989). Real-time scheduling of an automated manufacturing center. European Journal of Operational Research, 40(2), 222-242. · Zbl 0665.90047 · doi:10.1016/0377-2217(89)90332-9 |
| [53] | Sawicki, J. (1973). The problems of tardiness and saturation in a multi-class queue with sequence-dependent setups. AIIE Transactions, 5(3), 250-255. · doi:10.1080/05695557308974909 |
| [54] | Schaller, J., & Gupta, J. (2008). Single machine scheduling with family setups to minimize total earliness and tardiness. European Journal of Operational Research, 187, 1050-1068. · Zbl 1137.90516 · doi:10.1016/j.ejor.2006.06.061 |
| [55] | Schmidt, G. (2000). Scheduling with limited machine availability. European Journal of Operational Research, 121, 1-15. · Zbl 0959.90023 · doi:10.1016/S0377-2217(98)00367-1 |
| [56] | Sels, V., & Vanhoucke, M. (2012). A hybrid genetic algorithm for the single machine maximum lateness problem with release times and family setups. Computers & Operations Research, 39, 2346-2358. · Zbl 1251.90008 |
| [57] | Shabtay, D., & Steiner, G. (2007a). Single machine batch scheduling to minimize total completion time and resource consumption costs. Journal of Scheduling, 10, 255-261. · Zbl 1168.90469 · doi:10.1007/s10951-007-0025-9 |
| [58] | Shabtay, D., & Steiner, G. (2007b). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155, 1643-1666. · Zbl 1119.90022 · doi:10.1016/j.dam.2007.02.003 |
| [59] | Shakhlevich, N., & Strusevich, V. (2006). Single machine scheduling with controllable release and processing parameters. Discrete Applied Mathematics, 154(15), 2178-2199. · Zbl 1111.90045 · doi:10.1016/j.dam.2005.04.014 |
| [60] | Sourd, F. (2005). Earliness-tardiness scheduling with setup considerations. Computers & Operations Research, 32, 1849-1865. · Zbl 1075.90032 · doi:10.1016/j.cor.2003.12.002 |
| [61] | Sourd, F. (2006). Dynasearch for the earliness-tardiness scheduling problem with release dates and setup constraints. Operations Research Letters, 34, 591-598. · Zbl 1152.90468 · doi:10.1016/j.orl.2005.06.005 |
| [62] | Subramanian, K., Rawlings, J. B., Maravelias, C. T., Flores-Cerrillo, J., & Megan, L. (2013). Integration of control theory and scheduling methods for supply chain management. Computers and Chemical Engineering, 51, 4-20. · doi:10.1016/j.compchemeng.2012.06.012 |
| [63] | Sun, X., & Noble, J. (1999). An approach to job shop scheduling with sequence-dependent setups. Journal of Manufacturing Systems, 18(6), 416-430. · doi:10.1016/S0278-6125(00)87643-8 |
| [64] | Tseng, C. T., Liao, C. J., & Huang, K. L. (2009). Minimizing total tardiness on a single machine with controllable processing times. Computers & Operations Research, 36, 1852-1858. · Zbl 1179.90159 · doi:10.1016/j.cor.2008.05.009 |
| [65] | Uzsoy, R., & Velásquez, J. (2008). Heuristics for minimizing maximum lateness on a single machine with family-dependent set-up times. Computers & Operations Research, 35, 2018-2033. · Zbl 1139.90013 · doi:10.1016/j.cor.2006.10.003 |
| [66] | Vickson, R. G. (1980a). Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine. Operations Research, 28(5), 1155-1167. · Zbl 0449.90054 · doi:10.1287/opre.28.5.1155 |
| [67] | Vickson, R. G. (1980b). Two single machine sequencing problems involving controllable job processing times. AIIE Transactions, 12(3), 258-262. · doi:10.1080/05695558008974515 |
| [68] | Vieira, G. E., Herrmann, J. W., & Lin, E. (2003). Rescheduling manufacturing systems: a framework of strategies, policies, and methods. Journal of scheduling, 6, 39-62. · Zbl 1154.90500 · doi:10.1023/A:1022235519958 |
| [69] | Wilbrecht, J., & Prescott, W. (1969). The influence of setup time on job shop performance. Management Science, 16(4), B274-B280. · doi:10.1287/mnsc.16.4.B274 |
| [70] | Woodruff, D., & Spearman, M. (1992). Sequencing and batching for two classes of jobs with deadlines and setup times. Production and Operations Management, 1(1), 87-102. · doi:10.1111/j.1937-5956.1992.tb00341.x |
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.
