Abstract
We study a single-machine earliness–tardiness scheduling problem with due date assignment, in which the processing time of a job is a function of its starting time and its resource allocation. We analyze the problem with two different processing time functions and three different due date assignment methods. The goal is to minimize an integrated objective function, which includes earliness, tardiness, due date assignment, and total resource consumption costs. For each combination of due date assignment method and processing time function, we provide a polynomial-time algorithm to find the optimal job sequence, due date values, and resource allocations.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Gawiejnowicz S (2008) Time-dependent scheduling. Springer, New York
Huang X, Wang M-Z (2011) Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties. Appl Math Model 35:1349–1353
Wang X-R, Huang X, Wang J-B (2011) Single-machine scheduling with linear decreasing deterioration to minimize earliness penalties. Appl Math Model 35:3509–3515
Wang J-B, Wang J-J, Ji P (2011) Scheduling jobs with chain precedence constraints and deteriorating Jobs. J Oper Res Soc 62:1765–1770
Zhao C-L, Tang H-Y (2011) A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints. Optim Lett 5:183–190
Huang X, Wang M-Z, Wang J-B (2011) Single machine group scheduling with both learning effects and deteriorating jobs. Comput Ind Eng 60:750–754
Ozturkoglu Y, Bulfin RL (2011) A unique integer mathematical model for scheduling deteriorating jobs with rate-modifying activities on a single machine. Int J Adv Manuf Technol 57:753–762
Lai P-J, Lee W-C, Chen H-H (2011) Scheduling with deteriorating jobs and past-sequence-dependent setup times. Int J Adv Manuf Technol 54:737–741
Wang L-Y, Feng E-M (2012) A note on single-machine scheduling problems with the effects of deterioration and learning. Int J Adv Manuf Technol 59:539–545
Shen P, Wei C-M, Wu Y-B (2012) A note on deteriorating jobs and learning effects on a single-machine scheduling with past-sequence-dependent setup times. Int J Adv Manuf Technol 58:723–725
Wei C-M, Wang J-B, Ji P (2012) Single-machine scheduling with time-and-resource-dependent processing times. Appl Math Model 36:792–798
Wang J-B, Wang M-Z (2012) Single-machine scheduling with nonlinear deterioration. Optim Lett 6:87–98
Wang J-B, Huang X, Wu Y-B, Ji P (2012) Group scheduling with independent setup times, ready times, and deteriorating job processing times. Int J Adv Manuf Technol 60:643–649
Sun L-H, Sun L-Y, Wang M-Z, Wang J-B (2012) Flow shop makespan minimization scheduling with deteriorating jobs under dominating machines. Int J Prod Econ 138:195–200
Bai J, Li Z-R, Huang X (2012) Single-machine group scheduling with general deterioration and learning effects. Appl Math Model 36:1267–1274
Wang J-B, Wang M-Z, Ji P (2012) Single machine total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs. Int J Syst Sci 43:861–868
Huang X, Wang M-Z, Ji P (2012) Parallel machines scheduling with deteriorating and learning effects. Optim Lett. doi:10.1007/s11590-012-0490-8
Wang J-B, Ji P, Cheng TCE, Wang D (2012) Minimizing makespan in a two-machine flow shop with effects of deterioration and learning. Optim Lett 6:1393–1409
Wang X-R, Wang J-J (2012) Single-machine scheduling with convex resource dependent processing times and deteriorating jobs. Appl Math Model. doi:10.1016/j.apm.2012.05.025
Lee H-T, Yang D-L, Yang S-J (2012) Multi-machine scheduling with deterioration effects and maintenance activities for minimizing the total earliness and tardiness costs. Int J Adv Manuf Technol. doi:10.1007/s00170-012-4348-0
Shabtay D, Steiner G (2007) A survey of scheduling with controllable processing times. Discret Appl Math 155:1643–1666
Wang J-B, Xia Z-Q (2007) Single machine scheduling problems with controllable processing times and total absolute differences penalties. Eur J Oper Res 177:638–645
Shabtay D, Steiner G (2008) The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times. Ann Oper Res 159:25–40
Tseng C-T, Liao C-T, Huang K-L (2009) Minimizing total tardiness on a single machine with controllable processing times. Comput Oper Res 36:1852–1858
Wang D, Wang M-Z, Wang J-B (2010) Single-machine scheduling with learning effect and resource-dependent processing times. Comput Ind Eng 59:458-462
Koulamas C, Gupta S, Kyparisis GJ (2010) A unified analysis for the single-machine scheduling problem with controllable and non-controllable variable job processing times. Eur J Oper Res 205:479–482
Leyvand Y, Shabtay D, Steiner G (2010) A unified approach for scheduling with convex resource consumption functions using positional penalties. Eur J Oper Res 206:301–312
Zhu Z, Sun L, Chu F, Liu M (2011) Single-machine group scheduling with resource allocation and learning effect. Comput Ind Eng 60:148-157
Yin N, Wang X-Y (2011) Single-machine scheduling with controllable processing times and learning effect. Int J Adv Manuf Technol 54:743–748
Wang J-B, Wang M-Z (2012) Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time. Comput Oper Res 39:492–497
Lu Y-Y, Li G, Wu Y-B, Ji P (2012) Optimal due-date assignment problem with learning effect and resource-dependent processing times. Optim Lett. doi:10.1007/s11590-012-0467-7
Gordon VS, Proth JM, Chu CB (2002) A survey of the state-of-the-art of common due date assignment and scheduling research. Eur J Oper Res 139:1–25
Panwalker SS, Smith ML, Seidmann A (1982) Common due-date assignment to minimize total penalty for the one machine scheduling problem. Oper Res 30:391–399
Adamopoulos GI, Pappis CP (1996) Single machine scheduling with flow allowances. J Oper Res Soc 47:1280–1285
Seidmann A, Panwalkar SS, Smith ML (1981) Optimal assignment of due dates for a single processor scheduling problem. Int J Prod Res 19:393–399
Hardy GH, Littlewood JE, Polya G (1967) Inequalities. Cambridge University Press, Cambridge
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, XY., Wang, JJ. Single-machine due date assignment problem with deteriorating jobs and resource-dependent processing times. Int J Adv Manuf Technol 67, 255–260 (2013). https://doi.org/10.1007/s00170-013-4771-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-013-4771-x