Minmax Common Due-Window Assignment Scheduling with Deteriorating Jobs

doi:10.1007/s40305-023-00511-2

Abstract

Abstract: This paper investigates the common due-window assignment scheduling problem with deteriorating jobs on a single machine in which the processing time of a job is a proportional function of its starting time. The goal is to minimize the maximum value of earliness and tardiness penalties, as well as due-window location cost, and size cost. Depending on whether the location and size of due-window are known, this paper studies three relevant cases, all of which are solvable in polynomial time.

Key words: Scheduling, Single machine, Deteriorating jobs, Common due-window, Earliness, Tardiness

CLC Number:

90B35
68M20

Dan-Yang Lv, Jing Xue, Ji-Bo Wang. Minmax Common Due-Window Assignment Scheduling with Deteriorating Jobs[J]. Journal of the Operations Research Society of China, 2024, 12(3): 681-693.

TrendMD

References

[1] Pei, J., Zhou, Y., Yan, P., Pardalos, P.M.: A concise guide to scheduling with learning and deteriorating effects. Int. J. Prod. Res. 61, 2010-2031(2022)
[2] Geurtsen, M., Didden, J.B.H.C., Adan, J., Atan, Z., Adan, I.: Production, maintenance and resource scheduling: a review. Eur. J. Oper. Res. 305, 501-529(2023)
[3] Agnetis, A., Billaut, J.C., Gawiejnowicz, S., Pacciarelli, D.: Multiagent Scheduling. Springer, Berlin (2014)
[4] Gawiejnowicz, S.: Models and Algorithms of Time-Dependent Scheduling. Springer, Berlin (2020)
[5] Gawiejnowicz, S.: A review of four decades of time-dependent scheduling: main results, new topics, and open problems. J. Sched. 23, 3-47(2020)
[6] Wang, J.-B., Wang, J.-J., Ji, P.: Scheduling jobs with chain precedence constraints and deteriorating jobs. J. Oper. Res. Soci. 62, 1765-1770(2011)
[7] Miao, C.-X.: Complexity of scheduling with proportional deterioration and release dates. Iran. J. Sci. Technol. Trans. A Sci. 42, 1337-1342(2018)
[8] Li, D.-W., Lu, X.-W.: Parallel-batch scheduling with deterioration and rejection on a single machine. Appl. Math. A J. Chin. Univ. 35, 141-156(2020)
[9] Gordon, V.S., Proth, J.M., Chu, C.B.: A survey of the state of-the-art of common due date assignment and scheduling research. Eur. J. Oper. Res. 139, 1-25(2002)
[10] Gordon, V.S., Proth, J.M., Chu, C.B.: Due date assignment and scheduling: SLK, TWK and other due date assignment models. Prod. Plann. Control 13, 117-132(2002)
[11] Janiak, A., Janiak, W.A., Krysiak, T., Kwiatkowski, T.: A survey on scheduling problems with due windows. Eur. J. Oper. Res. 242, 347-357(2015)
[12] Ji, M., Yao, D., Yang, Q., Cheng, T.C.E.: Single-machine common flow allowance scheduling with aging effect, resource allocation, and a rate-modifying activity. Int. Trans. Oper. Res. 22, 997-1015(2015)
[13] Li, W.-D.: Improved approximation schemes for early work scheduling on identical parallel machines with a common due date. J. Oper. Res. Soc. China (2022). https://doi.org/10.1007/s40305-022-00402-y
[14] Liman, S.D., Panwalkar, S.S., Thongmee, S.: Common due window size and location determination in a single machine scheduling problem. J. Oper. Res. Soc. 49, 1007-1010(1998)
[15] Józefowska, J.: Just-In-Time Scheduling: Models and Algorithms for Computer and Manufacturing Systems. Springer, Berlin (2007)
[16] Yin, Y., Wang, D., Cheng, T.C.E.: Due Date-Related Scheduling with Two Agents. Springer, Berlin (2020)
[17] Yu, Y., Lu, Z., Sun, S.-J., He, L.-M., Hu, J.-D.: Scheduling problems on tardiness penalty and earliness award with simply linear processing time. J. Shanghai Univ. 13, 123-128(2009)
[18] Zhang, L., Zhang, Y.-Z., Bai, Q.-G.: An approximation algorithm for a supply-chain scheduling problem with an assignable common due window and holding time. J. Comb. Optim. 44, 2167-2179(2022)
[19] Qian, J., Han, H.: The due date assignment scheduling problem with the deteriorating jobs and delivery time. J. Appl. Math. Comput. 68, 2173-2186(2022)
[20] Mosheiov, G.: A due-window determination in minmax scheduling problems. INFOR 39, 107-123(2001)
[21] Mosheiov, G., Sarig, A.: Minmax scheduling problems with a common due-window. Comput. Oper. Res. 36, 1886-1892(2009)
[22] Mor, B., Mosheiov, G.: Minmax scheduling problems with common flow-allowance. J. Oper. Res. Soc. 63, 1284-1293(2012)
[23] Mosheiov, G., Sarig, A., Strusevich, V.: Minmax scheduling and due-window assignment with position-dependent processing times and job rejection. 4OR 18, 439-456(2020)
[24] Gawiejnowicz, S., Kononov, A.: Isomorphic scheduling problems. Ann. Oper. Res. 213, 131-145(2014)