Abstract
This paper considers single-machine scheduling problems with group technology (GT). We consider the case of group setup times and job processing times are a decreasing function of their starting time. We first prove that the makespan minimization problem remains polynomially solvable under the general decreasing linear deterioration. We then prove that the total weighted completion time minimization problem remains polynomially solvable under the proportional decreasing linear deterioration.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Browne S, Yechiali U (1990) Scheduling deteriorating jobs on a single processor. Oper Res 38:495–498
Mosheiov G (1991) V-shaped policies for scheduling deteriorating jobs. Oper Res 39:979–991
Mosheiov G (1994) Scheduling jobs under simple linear deterioration. Comput Oper Res 21:653–659
Sundararaghavan PS, Kunnathur AS (1994) Single machine scheduling with start time dependent processing times: some solvable cases. Eur J Oper Res 78:394–403
Chen Z-L (1996) Parallel machine scheduling with time dependent processing times. Discrete Appl Math 70:81–94
Hsieh YC, Bricker DL (1997) Scheduling linearly deteriorating jobs on multiple machines. Comput Ind Eng 32:727–734
Mosheiov G (1998) Multi-machine scheduling with linear deterioration. INFOR 36:205–214
Mosheiov G (2002) Complexity analysis of job-shop scheduling with deteriorating jobs. Discrete Appl Math 117:195–209
Kononov A, Gawiejnowicz S (2001) NP-hard cases in scheduling deteriorating jobs on dedicated machines. J Oper Res Soc 52:708–717
Ho KI-J, Leung JY-T, Wei W-D (1993) Complexity of scheduling tasks with time-dependent execution times. Inf Process Lett 48:315–320
Ng CT, Cheng TCE, Bachman A, Janiak A (2002) Three scheduling problems with deteriorating jobs to minimize the total completion time. Inf Process Lett 81:327–333
Bachman A, Cheng TCE, Janiak A, Ng CT (2002) Scheduling start time dependent jobs to minimize the total weighted completion time. J Oper Res Soc 53:688–693
Wang J-B, Xia Z-Q (2005) Scheduling jobs under decreasing linear deterioration. Inf Process Lett 94:63–69
Wang J-B (2007) Flow shop scheduling problems with decreasing linear deterioration under dominant machines. Comput Oper Res 34:2043–2058
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
Wu C-C, Lee W-C, Shiau Y-R (2007) Minimizing the total weighted completion time on a single machine under linear deterioration. Int J Adv Manuf Technol 33:1237–1243
Lee W-C, Wu C-C, Wen C-C, Chung Y-H (2008) A two-machine flowshop makespan scheduling problem with deteriorating jobs. Comput Ind Eng 54(4):737–749
Lee W-C, Wu C-C, Chung Y-H (2008) Scheduling deteriorating jobs on a single machine with release times. Comput Ind Eng 54(3):441–452
Lee W-C, Wu C-C (2008) Multi-machine scheduling with deteriorating jobs and scheduled maintenance. Appl Math Model 32(3):362–373
Lee W-C, Wu C-C, Liu H-C (2008) A note on single-machine makespan problem with general deteriorating function. Int J Adv Manuf Technol 40:1053–1056
Gao W-J, Huang X, Wang J-B (2009) Single-machine scheduling with precedence constraints and decreasing start-time dependent processing times. Int J Adv Manuf Technol. doi:10.1007/s00170-009-2089-5
Wang D, Wang J-B (2009) Single-machine scheduling with simple linear deterioration to minimize earliness penalties. Int J Adv Manuf Technol. doi:10.1007/s00170-009-2086-8
Huang X, Wang J-B, Wang X-R (2009) A generalization for single-machine scheduling with deteriorating jobs to minimize earliness penalties. Int J Adv Manuf Technol. doi:10.1007/s00170-009-2242-1
Wu C-C, Shiau Y-R, Lee W-C (2008) Single-machine group scheduling problems with deterioration consideration. Comput Oper Res 35:1652–1659
Wu C-C, Lee W-C (2008) Single-machine group scheduling problems with deteriorating setup times and job processing times. Int J Prod Econ 115(1):128–133
Wang J-B, Lin L, Shan F (2008) Single-machine group scheduling problems with deteriorating jobs. Int J Adv Manuf Technol 39:808–812
Wang J-B, Gao W-J, Wang L-Y, Wang D (2009) Single machine group scheduling with general linear deterioration to minimize the makespan. Int J Adv Manuf Technol 43:146–150
Burbidge JL (1979) Group technology in the engineer industry. Mechanical Engineering, London
Ham I, Hitomi K, Yoshida T (1985) Group technology: applications to production management. Kluwer-Nijhoff, Boston
Ng CT, Cheng TCE, Janiak A, Kovalyov MY (2005) Group scheduling with controllable setup and processing times: minimizing total weighted completion time. Ann Oper Res 133:163–147
Potts CN, Van Wassenhove LN (1992) Integrating scheduling with batching and lot-sizing: a review of algorithms and complexity. J Oper Res Soc 43:395–406
Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287–326
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, JB., Sun, L. Single-machine group scheduling with linearly decreasing time-dependent setup times and job processing times. Int J Adv Manuf Technol 49, 765–772 (2010). https://doi.org/10.1007/s00170-009-2444-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-009-2444-6