Abstract
This paper addresses job scheduling problems with parallel machines. To satisfy customers better in a manufacturing company, meeting due dates has been an important performance metric. Besides the numerous other factors affecting due date satisfaction, the splitting of a job through parallel machines can contribute to the reduction of production lead time, resulting in less job tardiness against their due dates. Thus, this paper presents heuristic algorithms for minimizing total tardiness of jobs to meet their due dates in a manufacturing shop with identically functioning machines. The algorithms take into account job splitting and sequence-dependent major/minor setup times. The performance of the proposed heuristics is compared with that of past three algorithms in the literature.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Balasubramanian H, Mönch L, Fowler J, Pfund M (2004) Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness. Int J Prod Res 42(8):1621–1638
Beraldi P, Ghianib G, Griecob A, Guerrierob E (2008) Rolling-horizon and fix-and-relax heuristics for the parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs. Comput Oper Res 35:3644–3656
Chen J (2009) Scheduling on unrelated parallel machines with sequence- and machine-dependent setup times and due-date constraints. Int J Adv Manuf Technol 44:1204–1212
Coffman EG, Bruno JL (1976) Computer and job shop scheduling theory. Wiley, New York
Dogramaci A, Surkis J (1979) Evaluation of a heuristic for scheduling independent jobs on parallel identical processors. Manag Sci 25:1208–1216
Jia J, Mason SJ (2009) Semiconductor manufacturing scheduling of jobs containing multiple orders on identical parallel machines. Int J Prod Res 47(10):2565–2585
Kim DW, Kim KH, Jang WS, Chen FF (2002) Unrelated parallel machine scheduling with setup times using simulated annealing. Rob Comput Integr Manuf 18(3–4):223–231
Kim YD, Shim SO, Kim SB, Choi YC, Yoon HM (2004) Parallel machine scheduling considering a job-splitting property. Int J Prod Res 42(21):4531–4546
Lee YH, Pinedo M (1997) Scheduling jobs on parallel machines with sequence-dependent setup times. Eur J Oper Res 100:464–474
Logendran R, Subur F (2004) Unrelated parallel machine scheduling with job splitting. IIE Trans 36:359–372
Mason SJ, Jin S, Jampani J (2009) A moving block heuristic to minimise earliness and tardiness costs on parallel machines. Int J Prod Res 47(19):5377–5390
Radhakrishnan S, Ventura JA (2000) Simulated annealing for parallel machine scheduling with earliness-tardiness penalties and sequence-dependent set-up times. Int J Prod Res 38(10):2233–2252
Rajgopal J, Bidanda B (1991) On scheduling parallel machines with two setup classes. Int J Prod Res 29(12):2443–2458
Serafini P (1996) Scheduling jobs on several machines with the job splitting property. Oper Res 44(4):617–628
Shim SO, Kim YD (2008) A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property. Comput Oper Res 35(3):863–875
So KC (1990) Some heuristics for scheduling jobs on parallel machines with setups. Manag Sci 36(4):467–475
Tahar DN, Yalaoui F, Chu C, Amodeo L (2006) A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times. Int J Prod Econ 99:63–73
Wittrock RJ (1990) Scheduling parallel machines with major and minor setup times. Int J Flex Manuf Syst 2:329–341
Xing W, Zhang J (2000) Parallel machine scheduling with splitting jobs. Discret Appl Math 103:259–269
Yalaoui F, Chu C (2003) An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times. IIE Trans 35:183–190
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Park, T., Lee, T. & Kim, C.O. Due-date scheduling on parallel machines with job splitting and sequence-dependent major/minor setup times. Int J Adv Manuf Technol 59, 325–333 (2012). https://doi.org/10.1007/s00170-011-3489-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-011-3489-x