Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines

Panneerselvam Senthilkumar, Sockalingam Narayanan

.

DOI: 10.4236/iim.2010.28056                

Abstract

This paper presents a survey of single machine scheduling problem with uniform parallel machines. The single machine scheduling problem with uniform parallel machines consists of n jobs, each with single operation, which are to be scheduled on m parallel machines with different speeds. These parallel machines are also called proportional machines or related machines. There are several measures of performance which are to be optimized in uniform parallel machines scheduling. Since, this scheduling problem is a combinatorial problem; usage of a heuristic is inevitable to obtain solution in polynomial time. This paper gives a classification of the literatures of this scheduling problem in three major categories, viz. offline scheduling, online scheduling and miscellaneous scheduling. In total, the available literatures are classified into 17 subgroups. Under each of the first two categories, the available literatures are discussed under different groups based on different measures of performance and non-preemptive/preemptive nature of the jobs. In the last category, the literatures are discussed under three subgroups, namely non-preemptive jobs, preemptive jobs and periodic jobs.

Keywords

Uniform Parallel Machines, Measure of Performance, Heuristic, Model, Competitive Ratio

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	R. Panneerselvam, “Production and Operations Management,” 2nd Edition, Prentice-Hall of India, New Delhi, 2005.
[2]	E. G. Jr. Coffman and R. L. Graham, “Optimal Scheduling for Two-Processor Systems,” Acta Informatica, Vol. 1, No. 3, 1972, pp. 200-213.
[3]	E. Horowiz and S. Sahni, “Exact and Approximate Algorithms for Scheduling Nonidentical Processors,” Journal of the ACM, Vol. 23, No. 2, 1976, pp. 317-327.
[4]	O. H. Ibarra and C. E. Kim, “Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors,” Journal of the ACM, Vol. 24, No. 2, 1977, pp. 280-289.
[5]	D. Prabuddha and E. M. Thomas, “Scheduling to Minimize Makespan on Unequal Parallel Processors,” Decision Sciences, Vol. 11, No. 4, 1980, pp. 586-602.
[6]	R. L. Bulfin, and R. G. Parker, “Scheduling Jobs on Two Facilities to Minimize Makespan,” Management Science, Vol. 26, No. 2, 1980, pp. 202-214.
[7]	D. K. Friesen and M. A. Langston, “Bounds for Multifit Scheduling on Uniform Processors,” SIAM Journal on Computing, Vol. 12, 1983, pp. 60-70.
[8]	R. L. Graham, “Bounds for Multiprocessing Timing Anomalies,” SIAM Journal of Applied Mathematics, Vol. 17, No. 2, 1969, pp. 416-429.
[9]	D. Gregory, “Scheduling Independent Tasks on Uniform Processors,” SIAM Journal of Computing, Vol. 13, No. 4, 1984, pp. 705-716.
[10]	D.K. Friesen, “Tighter Bounds for LPT Scheduling on Uniform Processors,” SIAM Journal on Computing, Vol. 16, No. 3, 1987, pp. 554-560.
[11]	D. S. Hochbaum and D. B. Shmoys, “A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach,” SIAM Journal on Computing, Vol. 17, No. 3, 1988, pp. 539-551.
[12]	B. Chen, “Parametric Bounds for LPT Scheduling on Uniform Processors,” Acta Mathematicae Applicateae, Sinica, Vol. 7, No. 1, 1991, pp. 67-73.
[13]	P. Mireault, J. B. Orlin and R. V. Vohra, “A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines,” Operations Research, Vol. 45, No. 1, 1997, pp. 116-125.
[14]	R. E. Burkard and Y. He, “A Note on MULTIFIT Scheduling for Uniform Machines,” Computing, Vol. 61, No. 3, 1998, pp. 277-283.
[15]	M. Y. Kovalyov and Y. M. Shafransky, “Uniform Machine Scheduling of Unit-Time Jobs Subject to Resource Constraints,” Discrete Applied Mathematics, Vol. 84, No. 1-3, 1998, pp. 253-257.
[16]	R. E. Burkard, Y. He and H. Kellerer, “A Linear Compound Algorithm for Uniform Machine Scheduling,” Computing, Vol. 61, No. 1, 1998, pp. 1-9.
[17]	R. Panneerselvam and S. Kanagalingam, “Modelling Parallel Processors with Different Processing Speeds of Single Machine Scheduling Problem to Minimize Make- span,” Industrial Engineering Journal, Vol. 17, No. 6, 1998, pp. 16-19.
[18]	R. Panneerselvam and S. Kanagalingam, “Simple Heuristic for Single Machine Scheduling Problem with Two Parallel Processors Having Varying Speeds to Minimize Makespan,” Industrial Engineering Journal, Vol. 18, No. 6, 1999, pp. 2-8.
[19]	C. Chekuri and M. Bender, “An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines,” Proceedings of IPCO’99, LNCS, 1999, pp. 383-393.
[20]	G. J. Woeginger, “A Comment on Scheduling on Uniform Machines under Chain-Type Precedence Constraints,” Operations Research Letters, Vol. 26, No. 3, 2000, pp. 107-109.
[21]	F. A. Chudak and D. B. Shmoys, “An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines,” Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 1997, pp. 581-590.
[22]	J. Jaffe, “Efficient Scheduling of Tasks without Full Use of Processor Resources,” Theoretical Computer Science, Vol. 26, No. 1, 1980, pp. 22-35.
[23]	C. Chekuri and M. Bender, “An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines,” Journal of Algorithms, Vol. 41, No. 2, 2001, 212-224.
[24]	C. J. Liao and C.-H. Lin, “Makespan Minimization for Two Uniform Parallel Machines,” International Journal of Production Economics, Vol. 84, No. 2, 2003, pp. 205- 213.
[25]	L. Epstein and J. Sgall, “Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines,” Proceedings of 7th Annual European Symposium on Algorithms, 1999, pp. 151-162.
[26]	L. Epstein and J. Sgall, “Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines,” Algorithmica, Vol. 39, No. 1, 2004, pp. 43- 57.
[27]	C. Koulamas and George J. Kyparisis, “Makespan Minimization on Uniform Parallel Machines with Release Times,” European Journal of Operational Research, Vol. 157, No. 1, 2004, pp. 262-266.
[28]	A. Agarwal, S. Colak, V. S. Jacob and H. Pirkul, “Heuristics and Augmented Neural Networks for Task Scheduling with Non-Identical Machines,” European Journal of Operational Research, Vol. 175, No. 1, 2006, pp. 296- 317.
[29]	C.-H. Lin and C.-J. Liao, “Makespan Minimization for Multiple Uniform Machines,” Computers & Industrial Engineering, Vol. 54, No. 4, 2008, pp. 983-992.
[30]	T. Kis, and R. Kapolnai, “Approximation and Auctions for Scheduling Batches on Related Machines,” Operations Research Letters, Vol. 35, No. 1, 2007, pp. 61-68.
[31]	S. T. McCormic and M. inedo, “Scheduling n Independent Jobs on m Uniform Machines with both Flow Time and Makespan Objectives: A Parametric Analysis,” ORSA Journal of Computing, Vol. 7, No. 1, 1995, pp. 63- 77.
[32]	C. U. Martel, “A parallel Algorithm for Preemptive Scheduling of Uniform Machines,” Journal of Parallel and Distributed Computing, Vol. 5, No. 6, 1988, pp. 700- 715.
[33]	T. Gonzalez and S. Sahni, “Preemptive Scheduling of Uniform Processor Systems,” Journal of Association of Computing Machinery, Vol. 25, No, 1, 1978, pp. 92-101.
[34]	H. Shachnai, T. Tamir and G. J. Woeginger, “Minimizing Makespan and Preemption Costs on a System of Uniform Machines,” Proceedings of the 10th European Symposium on Algorithms, 2002, pp. 859-871.
[35]	D. G. Pandelis, “Optimal Preemptive Scheduling on Uniform Machines with Discounted Flow Time Objectives,” European Journal of Operational Research, Vol. 177, No. 1, 2007, pp. 630-637.
[36]	M. I. Dessouky and R. L. Marcellus, “Scheduling Identical Jobs on Uniform Parallel Machines with Random Processing Times,” Computers and Industrial Engineering, Vol. 35, No. 1-2, 1998, pp. 109-112.
[37]	M. Azizoglu and O. Kirca, “On the Minimization of Total Weighted Flow Time with Identical and Uniform Parallel Machines,” European Journal of Operational Research, Vol. 113, No. 2, 1999, pp. 91-100.
[38]	Z.-L. Chen and W. B. Powell, “Solving Parallel Machine Scheduling Problems by Column Generation,” INFORMS Journal on Computing, Vol. 11, 1999, pp. 78-94.
[39]	T. F. Gonzalez, Y. T. L. Joseph and M. Pinedo, “Minimizing Total Completion Time on Uniform Machines with Deadline Constraints,” ACM Transactions on Algorithms, Vol. 2, No. 1, 2006, pp. 95-115.
[40]	J. Y. T. Leung, H. B. Li, M. Pinedo and J. W. Zhang, “Minimizing Total Weighted Completion Time when Scheduling Orders in a Flexible Environment with Uniform Machines,” Information Processing Letters, Vol. 103, No. 3, 2007, pp. 119-129.
[41]	K.-S. Lin, “Scheduling with Parallel Machines to Minimize Total Job Tardiness,” Engineering Costs and Production Economics, Vol. 5, No. 3-4, 1981, pp. 289-296.
[42]	A. Guinet, “Scheduling Independent Jobs on Uniform Parallel Machines to Minimize Tardiness Criteria,” Journal of Intelligent Manufacturing, Vol. 6, No. 2, 1995, pp. 95- 103.
[43]	M. Azizoglu and O. Kirca, “Tardiness Minimization on Parallel Machines,” International Journal of Production Economics, Vol. 55, No. 2, 1998, pp. 163-168.
[44]	I. Naofumi, T. Shunji and A. Mitsuhiko, “Minimizing Total Tardiness on Uniform Parallel Machines under Human Resource Constraint,” Proceedings of the Annual Conference of the Institute of Systems, Control and Information Engineers, Vol. 47, 2003, pp. 419-420.
[45]	V. A. Armentano and M. F. de F. Filho, “Minimizing Total Tardiness in Parallel Machine Scheduling with Setup Times: An Adaptive Momory-Based GRASP Approach,” European Journal of Operations Research, Vol. 183, No. 1, 2007, pp. 100-114.
[46]	N. H. Tuong, A. Soukhal and J.-C. Billaut, “Uniform Parallel Machine Scheduling Problem with a Common Due Date to Minimize Total Weighted Tardiness,” MAPSP Conference, 2007.
[47]	G. Mosheiov and A. Sarig, “Due-Date Assignment on Uniform Machines,” European Journal of Operational Research, Vol. 193, No. 1, 2009, pp. 49-58.
[48]	A. Federgruen and H. Groenevelt, “Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques,” Management Science, Vol. 32, No. 3, 1986, pp. 341-349.
[49]	M. M. Dessouky, “Scheduling Identical Jobs with Unequal Ready Times on Uniform Parallel Machines to Minimize the Maximum Lateness,” Computers & Industrial Engineering, Vol. 34, No. 4, 1998, pp. 793-806.
[50]	D. Chhajed, “A Note on Minimizing the Maximum Deviation of Job Completion Time about a Common Due-Date,” Applied Mathematics Letters, Vol. 1, No. 2, 1988, pp. 161-163.
[51]	F. A. Chudak and D. B. Shmoys, “Approximation Algorithm for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds,” Journal of Algorithms, Vol. 20, No. 2, 1999, pp. 323-343.
[52]	C. Koulamas and G. J. Kyparisis, “Scheduling on Uniform Parallel Machines to Minimize Maximum Lateness,” Operations Research Letters, Vol. 26, No. 3, 2000, pp. 175-179.
[53]	M. Drozdowski, J. Blazewicz, P. Formanowicz, W. Kubiak and G. Schmidt, “Scheduling Preemptable Tasks on Uniform Processors with Limited Availability for Maximum Lateness Criterion,” 7th International Workshop on Project Management Scheduling, 2000, pp. 118-120.
[54]	A. J. Ruize-Torres, F. J. Lopez and J. C. Ho, “Scheduling Uniform Parallel Machines Subject to a Secondary Resource to Minimize the Number of Tardy Jobs,” European Journal of Operational Research, Vol. 179, No. 2, 2007, pp. 302-315.
[55]	E. L. Lawler and C. U. Martel, “Preemptive Scheduling of Two Uniform Machines to Minimize the Number of Late Jobs,” Operations Research, Vol. 37, No. 2, 1989, pp. 314-318.
[56]	J. Wein and D. P. Williamson, “On-Line Scheduling of Parallel Machines,” Technical Report, Institute of Technology, Cambridge Lab for Computer Science, Massachusetts, 1990, p. 18.
[57]	L. Epstein and J. Sgall, “A Lower Bound for On-Line Scheduling on Uniformly Related Machines,” Operations Research Letters, Vol. 26, No. 1, 2000, pp. 17-22.
[58]	Z. Tan and Y. He, “Semi-On-Line Scheduling with Ordinal Data on Two Uniform Machines,” Operations Research Letters, Vol. 28, No. 5, 2001, pp. 221-231.
[59]	S. Kontogiannis, “Multiple-Choice Assignments on Uniformly Related Machines,” ALCOM-FT Technical Report Series, 2002, pp. 2-39.
[60]	L. Epstein and L. M. Favrholdt, “Optimal Non-Preemptive Semi-Online Scheduling on Two Related Machines,” Journal of Algorithms, Vol. 57, No. 1, 2005, pp. 49-73.
[61]	T. C. E. Cheng, C. T. Ng and V. Kotov, “A New Algorithm for Online Uniform-Machine Scheduling to Minimize the Makespan,” Information Processing Letters, Vol. 99, No. 3, 2006, pp. 102-105.
[62]	S. Sahni and Y. Cho, “Scheduling Independent Tasks with Due Times on a Uniform Processor System,” Journal of the ACM, Vol. 27, No. 3, 1980, pp. 550-563.
[63]	R. Li and L. Shi, “An On-Line Algorithm for Some Uniform Processor Scheduling,” SIAM Journal of Computer, Vol. 27, No. 2, 1998, pp. 414-422.
[64]	E. Angelelli, M. G. Speranza and Z. Tuza, “Semi-Online Scheduling on Two Uniform Processors,” Theoretical Computer Science, Vol. 393, No. 1-3, 2008, pp. 211-219.
[65]	J. Wen, and D. Du, “Preemptive On-Line Scheduling for Two Uniform Processors,” Operations Research Letters, Vol. 23, 1998, pp. 113-116.
[66]	A. Vestjens, “Scheduling Uniform Machines On-Line Requires Nondecreasing Speed Ratios,” Mathematical Programming, Vol. 82, No. 2, 1998, pp. 225-234.
[67]	L. Epstein, J. Noga, S. S. Seiden, J. Sgall and G. J. Woeginger, “Randomized On-Line Scheduling on Two Uniform Machines,” Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, 1999, pp. 317-326.
[68]	L. Epstein, J. Noga, S. S. Seiden, J. Sgall and G. J. Woeginger, “Randomized On-Line Scheduling on Two Uniform Machines,” Journal of Scheduling, Vol. 4, No. 2, 2001, pp. 71-92.
[69]	L. Epstein, “Optimal Preemptive On-Line Scheduling on Uniform Processors with Non-Decreasing Speed Ratios,” Operations Research Letters, Vol. 29, No. 2, 2001(a), pp. 93-98.
[70]	L. Epstein, “Optimal Preemptive Scheduling on Uniform Processors with Non-Decreasing Speed Ratios,” Proceedings of 18th STACS, 2001(b), pp. 230-237.
[71]	L. Epstein and L. M. Favrholdt, “Optimal Preemptive Semi-Online Scheduling to Minimize Makespan on Two Related Machines,” Operations Research Letters, Vol. 30, No. 4, 2002, pp. 269-275.
[72]	D. L. Du, “Optimal Preemptive Semi-Online Scheduling on Two Uniform Processors,” Information Processing letters, Vol. 92, No. 5, 2004, pp. 219-223.
[73]	N. Balakrishnan, J. J. Kanet and S. Sridharan, “Early/Tardy Scheduling with Sequence Dependent Setups on Uniform Parallel Machines,” Computers & Operations Research, Vol. 26, No. 2, 1999, pp. 127-141.
[74]	U. Bilge, F. Kirac, M. Kurtulan and P. Pekgun, “A Tabu Search Algorithm for Parallel Machine Total Tardiness Problem,” Computers and Operations Research, Vol. 31, No. 3, 2004, pp. 397-414.
[75]	Y. Azar and L. Epstein, “On-Line Machine Covering,” Proceedings of 5th ESA conference, Graz, 1997, pp. 23- 36.
[76]	Y. Azar and L. Epstein, “On-Line Machine Covering, Journal of Scheduling,” Vol. 1, No. 2, 1998a, pp. 67-77.
[77]	Y. Azar and L. Epstein, “Approximation Schemes for Covering and Scheduling on Related Machines,” Proceedings of the 1st Workshop on Approximation Algori- thms for Combinatorial Optimization Problems (APPROX’98), in Lecture Notes in Computer Science, Springer-Verlag, Berlin, Vol. 1444, 1998b, pp. 39-47.
[78]	Z. Tan and Y. He and L. Epstein, “Optimal On-Line Algorithms for the Uniform Machine Scheduling Problem with Ordinal Data,” Information and Computation, Vol. 196, No. 1, 2005, pp. 57-70.
[79]	Y. He and Y. Jiang, “Optimal Semi-Online Preemptive Algorithms for Machine Covering on Two Uniform Machines,” Theoretical Computer Science, Vol. 339, No. 2-3, 2005, pp. 293-314.
[80]	B. Alidaee and A. Ahmadian, “Two Parallel Machine Sequencing Problems Involving Controllable Job Processing Times,” European Journal of Operational Research, Vol. 70, No. 3, 1993, pp. 335-341.
[81]	B. Alidaee and A. Ahmadian, “Scheduling on a Single Processor with Variable Speed,” Information Processing Letters, Vol. 60, No. 4, 1996, pp. 189-193.
[82]	S. Vahid, N. Mohmoud and K. Mohsen, “Deadline Scheduling with Processor Affinity and Feasibility Check on Uniform Machines,” Computer and Information Technology, Vol. 16-19, 2007, pp. 793-798.
[83]	O. B. Bekki and M. Azizoglu, “Operational Fixed Interval Scheduling Problem on Uniform Parallel Machines,” International Journal of Production Economics, Vol. 112, No. 2, 2008, pp. 756-768.
[84]	Y. He and X. Min, “On-Line Uniform Machine Scheduling with Rejection,” Computing, Vol. 65, No. 1, 2000, pp. 1-12.
[85]	J. Blazewicz, “Minimizing Mean Weighted Information Loss with Preemptable Tasks and Parallel Processors,” Technology and Science of Informatics, Vol. 3, No. 6, 1984, pp. 415-420.
[86]	J. Blazewicz and G. Finke, “Minimizing Mean Weighted Execution Time Loss on Identical and Uniform Processors,” Information processing Letters, Vol. 24, No. 4, 1987, pp. 259-263.
[87]	H. Ishi, C. Martel, T. Masuda and T. Nishida, “A Generalized Uniform Processor System,” Operations Research, Vol. 33, No. 2, 1985, pp. 346-362.
[88]	J. Blazewicz and P. Bouvry, F. Guinand and D. Trystram, “Scheduling Complete Intrees on Two Uniform Processors with Communication Delays,” Information Processing Letters, Vol. 58, No. 5, 1996, pp. 255-263.
[89]	N. V. Shakhlevich and V. A. Strusevich, “Preemptive Scheduling on Uniform Parallel Machines with Controllable Job Processing Times,” Algorithmica, Vol. 51, No. 4, 2007, pp. 451-473.
[90]	B. Kubiak, B. Penz and D. Trystram, “Scheduling Chains on Uniform Processors with Communication Delays,” Journal of Scheduling, Vol. 5, No. 6, 2002, pp. 459-476.
[91]	S. Baruah, “Scheduling Periodic Tasks on Uniform Multiprocessors,” Information Processing Letters, Vol. 80, No. 2, 2001, pp. 97-104.
[92]	S. Baruah and J. Goossens, “Rate-Monotonic Scheduling on Uniform Multiprocessors,” IEEE Transactions on Computers, Vol. 57, No. 7, 2003, pp. 966-970.