Scheduling Jobs on Dedicated Parallel Machines

Abstract:

This paper considers scheduling problem on dedicated parallel machines where several types of machines are grouped into one process. The dedicated machine is that a job with a specific recipe should be processed on the dedicated machine even though the job can be produced on any other machine originally. In this process, a setup is required when different jobs are done consecutively. To minimize the completion time of the last job, a scheduling method is developed. Computational experiments are performed on a number of test problems and results show that the suggested algorithm give good solutions in a reasonable amount of computation time.

• Periodical: Applied Mechanics and Materials (Volumes 433-435)
• Pages: 2363-2366
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.433-435.2363
• Online since: October 2013
• Authors: Sang Oh Shim, Seong Woo Choi*
• Keywords: Dedicated Parallel Machines, Scheduling

References

[1] Goemans, M.X., An approximation algorithm for scheduling on three dedicated machines, Discrete Applied Mathematics, Vol. 61, pp.49-59, (1995).

DOI: 10.1016/0166-218x(94)00160-f

[2] Kellerer, H. and Strusevich, V.A., Scheduling problems for parallel dedicated machines under multiple resource constraints, Discrete Applied Mathematics, Vol. 133, pp.45-68, (2004).

DOI: 10.1016/s0166-218x(03)00433-5

[3] Wu, M.C., Huang, Y.L., Chang, Y.C. and Yang, K.F., Dispatching in semiconductor fabs with machine-dedication features, International Journal of Advanced Manufacturing Technology, Vol. 28, pp.978-984, (2006).

DOI: 10.1007/s00170-004-2431-x

[4] Graham, R.L., Bounds on multiprocessor timing anomalies, SIAM Journal of Applied Mathematics, Vol. 17, pp.416-429, (1969).

DOI: 10.1137/0117039

[5] Allahverdi, A., Gupta, J.N.D. and Aldowaisan, T., A review of scheduling research involving setup considerations, OMEGA-The International Journal of Management Science, Vol. 27, pp.219-239, (1999).

DOI: 10.1016/s0305-0483(98)00042-5

[6] Tang, C.S. and Wittrock, R.J., Parallel machine scheduling with major and minor setups, York Town Heights, NY: RC 11412, IBM TJ Watson Research Center, (1985).

[7] So, K.C., Some heuristics for scheduling jobs on parallel machines with setups, Management Science, Vol. 36, pp.467-475, (1990).

DOI: 10.1287/mnsc.36.4.467

[8] Tang, C.S., Scheduling batches on parallel machines with major and minor setups, European Journal of Operational Research, Vol. 46, pp.28-37, (1990).

DOI: 10.1016/0377-2217(90)90295-m

[9] Lee, D.H. and Kim, Y.D., Scheduling algorithms for flexible manufacturing systems with partially grouped machines, Journal of Manufacturing Systems, Vol. 18, No. 4, pp.301-309, (1999).

DOI: 10.1016/s0278-6125(00)86632-7