Parallel task scheduling - Revision history

Citation bot: Alter: title, template type. Add: pages, chapter, isbn. Removed parameters. | Use this bot. Report bugs. | Suggested by Abductive | Category:Optimal scheduling | #UCB_Category 6/22

2025-02-16T13:30:50Z

Alter: title, template type. Add: pages, chapter, isbn. Removed parameters. | Use this bot. Report bugs. | Suggested by Abductive | Category:Optimal scheduling | #UCB_Category 6/22

← Previous revision		Revision as of 13:30, 16 February 2025
Line 42:		Line 42:
	== Algorithms ==		== Algorithms ==

	The list scheduling algorithm by Garey and Graham<ref>{{cite journal \|last1=Garey \|first1=M. R. \|last2=Graham \|first2=R. L. \|title=Bounds for Multiprocessor Scheduling with Resource Constraints \|journal=SIAM Journal on Computing \|date=1 June 1975 \|volume=4 \|issue=2 \|pages=187–200 \|doi=10.1137/0204015 \|issn=0097-5397\|doi-access=free }}</ref> has an absolute ratio <math>2</math>, as pointed out by Turek et al.<ref>{{cite journal \|last1=Turek \|first1=John \|last2=Wolf \|first2=Joel L. \|last3=Yu \|first3=Philip S. \|title=Approximate algorithms scheduling parallelizable tasks {{!}} Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures \|website=dl.acm.org \|doi=10.1145/140901.141909 \|s2cid=15607549 \|language=EN}}</ref> and Ludwig and Tiwari.<ref>{{cite journal \|last1=Ludwig \|first1=Walter \|last2=Tiwari \|first2=Prasoon \|title=Scheduling malleable and nonmalleable parallel tasks {{!}} Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms \|journal=Fifth Annual {ACM-SIAM} Symposium on Discrete Algorithms (SODA) \|date=1994 \|pages=167–176 \|url=http://dl.acm.org/citation.cfm?id=314464.314491 \|language=EN}}</ref>		The list scheduling algorithm by Garey and Graham<ref>{{cite journal \|last1=Garey \|first1=M. R. \|last2=Graham \|first2=R. L. \|title=Bounds for Multiprocessor Scheduling with Resource Constraints \|journal=SIAM Journal on Computing \|date=1 June 1975 \|volume=4 \|issue=2 \|pages=187–200 \|doi=10.1137/0204015 \|issn=0097-5397\|doi-access=free }}</ref> has an absolute ratio <math>2</math>, as pointed out by Turek et al.<ref>{{cite journal \|last1=Turek \|first1=John \|last2=Wolf \|first2=Joel L. \|last3=Yu \|first3=Philip S. \|title=Approximate algorithms scheduling parallelizable tasks {{!}} Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures \|website=dl.acm.org \|doi=10.1145/140901.141909 \|s2cid=15607549 \|language=EN}}</ref> and Ludwig and Tiwari.<ref>{{cite journal \|last1=Ludwig \|first1=Walter \|last2=Tiwari \|first2=Prasoon \|title=Scheduling malleable and nonmalleable parallel tasks {{!}} Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms \|journal=Fifth Annual {ACM-SIAM} Symposium on Discrete Algorithms (SODA) \|date=1994 \|pages=167–176 \|isbn=978-0-89871-329-9 \|url=http://dl.acm.org/citation.cfm?id=314464.314491 \|language=EN}}</ref>
	Feldmann, Sgall and Teng<ref>{{cite journal \|last1=Feldmann \|first1=Anja \|last2=Sgall \|first2=Jiří \|last3=Teng \|first3=Shang-Hua \|title=Dynamic scheduling on parallel machines \|journal=Theoretical Computer Science \|date=1 August 1994 \|volume=130 \|issue=1 \|pages=49–72 \|doi=10.1016/0304-3975(94)90152-X \|language=en \|issn=0304-3975\|doi-access=free }}</ref> observed that the length of a non-preemptive schedule produced by the list scheduling algorithm is actually at most <math>(2-1/m)</math> times the optimum preemptive makespan.		Feldmann, Sgall and Teng<ref>{{cite journal \|last1=Feldmann \|first1=Anja \|last2=Sgall \|first2=Jiří \|last3=Teng \|first3=Shang-Hua \|title=Dynamic scheduling on parallel machines \|journal=Theoretical Computer Science \|date=1 August 1994 \|volume=130 \|issue=1 \|pages=49–72 \|doi=10.1016/0304-3975(94)90152-X \|language=en \|issn=0304-3975\|doi-access=free }}</ref> observed that the length of a non-preemptive schedule produced by the list scheduling algorithm is actually at most <math>(2-1/m)</math> times the optimum preemptive makespan.
	A polynomial-time approximation scheme (PTAS) for the case when the number <math>m</math> of processors is constant, denoted by <math>Pm\|size_j\|C_{\max}</math>, was presented by Amoura et al.<ref>{{cite journal \|last1=Amoura \|first1=Abdel Krim \|last2=Bampis \|first2=Evripidis \|last3=Kenyon \|first3=Claire \|last4=Manoussakis \|first4=Yannis \|title=Scheduling Independent Multiprocessor Tasks \|journal=Algorithmica \|date=1 February 2002 \|volume=32 \|issue=2 \|pages=247–261 \|doi=10.1007/s00453-001-0076-9 \|s2cid=17256951 \|language=en \|issn=1432-0541}}</ref> and Jansen et al.<ref>{{cite journal \|last1=Jansen \|first1=Klaus \|last2=Porkolab \|first2=Lorant \|title=Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks \|journal=Algorithmica \|date=1 March 2002 \|volume=32 \|issue=3 \|pages=507–520 \|doi=10.1007/s00453-001-0085-8 \|language=en \|issn=1432-0541\|hdl=11858/00-001M-0000-0014-7B6C-D \|s2cid=2019475 \|hdl-access=free }}</ref>		A polynomial-time approximation scheme (PTAS) for the case when the number <math>m</math> of processors is constant, denoted by <math>Pm\|size_j\|C_{\max}</math>, was presented by Amoura et al.<ref>{{cite journal \|last1=Amoura \|first1=Abdel Krim \|last2=Bampis \|first2=Evripidis \|last3=Kenyon \|first3=Claire \|last4=Manoussakis \|first4=Yannis \|title=Scheduling Independent Multiprocessor Tasks \|journal=Algorithmica \|date=1 February 2002 \|volume=32 \|issue=2 \|pages=247–261 \|doi=10.1007/s00453-001-0076-9 \|s2cid=17256951 \|language=en \|issn=1432-0541}}</ref> and Jansen et al.<ref>{{cite journal \|last1=Jansen \|first1=Klaus \|last2=Porkolab \|first2=Lorant \|title=Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks \|journal=Algorithmica \|date=1 March 2002 \|volume=32 \|issue=3 \|pages=507–520 \|doi=10.1007/s00453-001-0085-8 \|language=en \|issn=1432-0541\|hdl=11858/00-001M-0000-0014-7B6C-D \|s2cid=2019475 \|hdl-access=free }}</ref>
Line 48:		Line 48:
	In this algorithm, the number of machines appears polynomially in the time complexity of the algorithm.		In this algorithm, the number of machines appears polynomially in the time complexity of the algorithm.
	Since, in general, the number of machines appears only in logarithmic in the size of the instance, this algorithm is a pseudo-polynomial time approximation scheme as well.		Since, in general, the number of machines appears only in logarithmic in the size of the instance, this algorithm is a pseudo-polynomial time approximation scheme as well.
	A <math>(3/2+\varepsilon)</math>-approximation was given by Jansen,<ref>{{cite ~~journal~~ \|last1=Jansen \|first1=Klaus \|~~title~~=A(3/2+ε) approximation algorithm for scheduling moldable and non-moldable parallel tasks ~~{{!}}~~ Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures \|~~journal~~=~~24th {ACM} Symposium on Parallelism in Algorithms and Architectures,{SPAA}~~ \|~~date~~=~~2012~~ \|doi=10.1145/2312005.2312048 \|s2cid=6586439 \|language=EN}}</ref> which closes the gap to the lower bound of <math>3/2</math> except for an arbitrarily small <math>\varepsilon</math>.		A <math>(3/2+\varepsilon)</math>-approximation was given by Jansen,<ref>{{cite book \|last1=Jansen \|first1=Klaus \|chapter=A <sub>(3/2+ε)</sub> approximation algorithm for scheduling moldable and non-moldable parallel tasks \|title=Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures \|date=2012 \|pages=224–235 \|doi=10.1145/2312005.2312048 \|isbn=978-1-4503-1213-4 \|s2cid=6586439 \|language=EN}}</ref> which closes the gap to the lower bound of <math>3/2</math> except for an arbitrarily small <math>\varepsilon</math>.

	== Differences between contiguous and non-contiguous jobs ==		== Differences between contiguous and non-contiguous jobs ==

Codename Noreste: Disruption.

2024-07-22T06:53:08Z

Disruption.

← Previous revision		Revision as of 06:53, 22 July 2024
Line 78:		Line 78:
	[[Category:Optimal scheduling]]		[[Category:Optimal scheduling]]
	[[Category:Packing problems]]		[[Category:Packing problems]]
	[[Category:NP-complete problems]]

999-Bandera Mouse: rezaty lahiv kak i rezaty tebe David Eppstein (talk)

2024-07-22T06:47:35Z

rezaty lahiv kak i rezaty tebe David Eppstein (talk)

← Previous revision		Revision as of 06:47, 22 July 2024
Line 78:		Line 78:
	[[Category:Optimal scheduling]]		[[Category:Optimal scheduling]]
	[[Category:Packing problems]]		[[Category:Packing problems]]
			[[Category:NP-complete problems]]

David Eppstein: Reverted edit by 666-Bandera Mouse (talk) to last version by Kaltenmeyer

2024-07-18T08:01:59Z

Reverted edit by 666-Bandera Mouse (talk) to last version by Kaltenmeyer

← Previous revision		Revision as of 08:01, 18 July 2024
Line 78:		Line 78:
	[[Category:Optimal scheduling]]		[[Category:Optimal scheduling]]
	[[Category:Packing problems]]		[[Category:Packing problems]]
	[[Category:NP-complete problems]]

666-Bandera Mouse at 07:35, 18 July 2024

2024-07-18T07:35:21Z

← Previous revision		Revision as of 07:35, 18 July 2024
Line 78:		Line 78:
	[[Category:Optimal scheduling]]		[[Category:Optimal scheduling]]
	[[Category:Packing problems]]		[[Category:Packing problems]]
			[[Category:NP-complete problems]]

Kaltenmeyer: Adding local short description: "Optimization problem in computer science", overriding Wikidata description "theoretical computer science"

2023-12-18T15:30:22Z

Adding local short description: "Optimization problem in computer science", overriding Wikidata description "theoretical computer science"

← Previous revision		Revision as of 15:30, 18 December 2023
Line 1:		Line 1:
			{{Short description\|Optimization problem in computer science}}
	'''Parallel task scheduling''' (also called '''parallel job scheduling<ref name="Johannes" /><ref name="PPTAS" />''' or '''parallel processing scheduling<ref name=":0" />''') is an [[optimization problem]] in [[computer science]] and [[Operations Research\|operations research]]. It is a variant of [[optimal job scheduling]]. In a general job scheduling problem, we are given ''n'' jobs ''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' of varying processing times, which need to be scheduled on ''m'' machines while trying to minimize the [[makespan]] - the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as ''parallel-task scheduling'', all machines are identical. Each job ''j'' has a ''length'' parameter ''p<sub>j</sub>'' and a ''size'' parameter ''q''<sub>j</sub>, and it must run for exactly ''p<sub>j</sub>'' time-steps on exactly ''q''<sub>j</sub> machines in ''parallel''.		'''Parallel task scheduling''' (also called '''parallel job scheduling<ref name="Johannes" /><ref name="PPTAS" />''' or '''parallel processing scheduling<ref name=":0" />''') is an [[optimization problem]] in [[computer science]] and [[Operations Research\|operations research]]. It is a variant of [[optimal job scheduling]]. In a general job scheduling problem, we are given ''n'' jobs ''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' of varying processing times, which need to be scheduled on ''m'' machines while trying to minimize the [[makespan]] - the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as ''parallel-task scheduling'', all machines are identical. Each job ''j'' has a ''length'' parameter ''p<sub>j</sub>'' and a ''size'' parameter ''q''<sub>j</sub>, and it must run for exactly ''p<sub>j</sub>'' time-steps on exactly ''q''<sub>j</sub> machines in ''parallel''.

OAbot: Open access bot: doi updated in citation with #oabot.

2023-08-13T21:44:41Z

Open access bot: doi updated in citation with #oabot.

← Previous revision		Revision as of 21:44, 13 August 2023
Line 3:		Line 3:
	Veltman et al.<ref>{{Cite journal\|last1=Veltman\|first1=B\|last2=Lageweg\|first2=B. J\|last3=Lenstra\|first3=J. K\|date=1990-12-01\|title=Multiprocessor scheduling with communication delays\|journal=Parallel Computing\|language=en\|volume=16\|issue=2\|pages=173–182\|doi=10.1016/0167-8191(90)90056-F\|issn=0167-8191\|url=https://ir.cwi.nl/pub/5713}}</ref> and Drozdowski<ref name=":0">{{Cite journal\|last=Drozdowski\|first=Maciej\|date=2009\|title=Scheduling for Parallel Processing\|journal=Computer Communications and Networks\|language=en-gb\|doi=10.1007/978-1-84882-310-5\|isbn=978-1-84882-309-9\|issn=1617-7975}}</ref> denote this problem by <math> P\|size_j\|C_{\max} </math> in the [[Notation for theoretic scheduling problems\|three-field notation]] introduced by Graham et al.<ref name="initial specification">{{cite conference\|last1=Graham\|first1=R. L.\|last2=Lawler\|first2=E. L.\|last3=Lenstra\|first3=J.K.\|last4=Rinnooy Kan\|first4=A.H.G.\|year=1979\|title=Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey\|url=http://mat.uab.es/~alseda/MasterOpt/79_03_scheduling_survey.pdf\|publisher=Elsevier\|pages=(5) 287–326\|book-title=Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium}}</ref> '''P''' means that there are several identical machines running in parallel; ''size<sub>j</sub>'' means that each job has a size parameter; ''C''<sub>max</sub> means that the goal is to minimize the maximum completion time. Some authors use <math> P\|m_j\|C_{\max} </math> instead.'''<ref name="Johannes" />''' Note that the problem of [[parallel-machines scheduling]] is a special case of parallel-task scheduling where <math> size_j=1 </math> for all ''j'', that is, each job should run on a single machine.		Veltman et al.<ref>{{Cite journal\|last1=Veltman\|first1=B\|last2=Lageweg\|first2=B. J\|last3=Lenstra\|first3=J. K\|date=1990-12-01\|title=Multiprocessor scheduling with communication delays\|journal=Parallel Computing\|language=en\|volume=16\|issue=2\|pages=173–182\|doi=10.1016/0167-8191(90)90056-F\|issn=0167-8191\|url=https://ir.cwi.nl/pub/5713}}</ref> and Drozdowski<ref name=":0">{{Cite journal\|last=Drozdowski\|first=Maciej\|date=2009\|title=Scheduling for Parallel Processing\|journal=Computer Communications and Networks\|language=en-gb\|doi=10.1007/978-1-84882-310-5\|isbn=978-1-84882-309-9\|issn=1617-7975}}</ref> denote this problem by <math> P\|size_j\|C_{\max} </math> in the [[Notation for theoretic scheduling problems\|three-field notation]] introduced by Graham et al.<ref name="initial specification">{{cite conference\|last1=Graham\|first1=R. L.\|last2=Lawler\|first2=E. L.\|last3=Lenstra\|first3=J.K.\|last4=Rinnooy Kan\|first4=A.H.G.\|year=1979\|title=Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey\|url=http://mat.uab.es/~alseda/MasterOpt/79_03_scheduling_survey.pdf\|publisher=Elsevier\|pages=(5) 287–326\|book-title=Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium}}</ref> '''P''' means that there are several identical machines running in parallel; ''size<sub>j</sub>'' means that each job has a size parameter; ''C''<sub>max</sub> means that the goal is to minimize the maximum completion time. Some authors use <math> P\|m_j\|C_{\max} </math> instead.'''<ref name="Johannes" />''' Note that the problem of [[parallel-machines scheduling]] is a special case of parallel-task scheduling where <math> size_j=1 </math> for all ''j'', that is, each job should run on a single machine.

	The origins of this problem formulation can be traced back to 1960.<ref>{{Cite journal\|last=Codd\|first=E. F.\|date=1960-06-01\|title=Multiprogram scheduling\|journal=Communications of the ACM\|language=EN\|volume=3\|issue=6\|pages=347–350\|doi=10.1145/367297.367317\|s2cid=14701351}}</ref> For this problem, there exists no polynomial time approximation algorithm with a ratio smaller than <math>3/2</math> unless <math>P=NP</math>.{{Citation needed\|date=June 2021}}		The origins of this problem formulation can be traced back to 1960.<ref>{{Cite journal\|last=Codd\|first=E. F.\|date=1960-06-01\|title=Multiprogram scheduling\|journal=Communications of the ACM\|language=EN\|volume=3\|issue=6\|pages=347–350\|doi=10.1145/367297.367317\|s2cid=14701351\|doi-access=free}}</ref> For this problem, there exists no polynomial time approximation algorithm with a ratio smaller than <math>3/2</math> unless <math>P=NP</math>.{{Citation needed\|date=June 2021}}

	== Definition ==		== Definition ==

Erel Segal at 18:54, 8 January 2023

2023-01-08T18:54:23Z

← Previous revision		Revision as of 18:54, 8 January 2023
Line 1:		Line 1:
	'''Parallel task scheduling''' (also called '''parallel job scheduling<ref name="Johannes" /><ref name="PPTAS" />''' or '''parallel processing scheduling<ref name=":0" />''') is an [[optimization problem]] in [[computer science]] and [[Operations Research\|operations research]]. It is a variant of [[optimal job scheduling]]. In a general job scheduling problem, we are given ''n'' jobs ''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' of varying processing times, which need to be scheduled on ''m'' machines while trying to minimize the [[makespan]] - the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as ''parallel-task scheduling'', all machines are identical. Each job ''j'' has a ''length'' parameter ''p<sub>j</sub>'' and a ''size'' parameter ''q''<sub>j</sub>, and it must run for exactly ''p<sub>j</sub>'' time-steps on exactly ''q''<sub>j</sub> machines in ''parallel''.		'''Parallel task scheduling''' (also called '''parallel job scheduling<ref name="Johannes" /><ref name="PPTAS" />''' or '''parallel processing scheduling<ref name=":0" />''') is an [[optimization problem]] in [[computer science]] and [[Operations Research\|operations research]]. It is a variant of [[optimal job scheduling]]. In a general job scheduling problem, we are given ''n'' jobs ''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' of varying processing times, which need to be scheduled on ''m'' machines while trying to minimize the [[makespan]] - the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as ''parallel-task scheduling'', all machines are identical. Each job ''j'' has a ''length'' parameter ''p<sub>j</sub>'' and a ''size'' parameter ''q''<sub>j</sub>, and it must run for exactly ''p<sub>j</sub>'' time-steps on exactly ''q''<sub>j</sub> machines in ''parallel''.

	Veltman et al.<ref>{{Cite journal\|last1=Veltman\|first1=B\|last2=Lageweg\|first2=B. J\|last3=Lenstra\|first3=J. K\|date=1990-12-01\|title=Multiprocessor scheduling with communication delays\|journal=Parallel Computing\|language=en\|volume=16\|issue=2\|pages=173–182\|doi=10.1016/0167-8191(90)90056-F\|issn=0167-8191\|url=https://ir.cwi.nl/pub/5713}}</ref> and Drozdowski<ref name=":0">{{Cite journal\|last=Drozdowski\|first=Maciej\|date=2009\|title=Scheduling for Parallel Processing\|journal=Computer Communications and Networks\|language=en-gb\|doi=10.1007/978-1-84882-310-5\|isbn=978-1-84882-309-9\|issn=1617-7975}}</ref> denote this problem by <math> P\|size_j\|C_{\max} </math> in the [[Notation for theoretic scheduling problems\|three-field notation]] introduced by Graham et al.<ref name="initial specification">{{cite conference\|last1=Graham\|first1=R. L.\|last2=Lawler\|first2=E. L.\|last3=Lenstra\|first3=J.K.\|last4=Rinnooy Kan\|first4=A.H.G.\|year=1979\|title=Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey\|url=http://mat.uab.es/~alseda/MasterOpt/79_03_scheduling_survey.pdf\|publisher=Elsevier\|pages=(5) 287–326\|book-title=Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium}}</ref> '''P''' means that there are several identical machines running in parallel; ''size<sub>j</sub>'' means that each job has a size parameter; ''C''<sub>max</sub> means that the goal is to minimize the maximum completion time. Some authors use <math> P\|m_j\|C_{\max} </math> instead.'''<ref name="Johannes" />'''		Veltman et al.<ref>{{Cite journal\|last1=Veltman\|first1=B\|last2=Lageweg\|first2=B. J\|last3=Lenstra\|first3=J. K\|date=1990-12-01\|title=Multiprocessor scheduling with communication delays\|journal=Parallel Computing\|language=en\|volume=16\|issue=2\|pages=173–182\|doi=10.1016/0167-8191(90)90056-F\|issn=0167-8191\|url=https://ir.cwi.nl/pub/5713}}</ref> and Drozdowski<ref name=":0">{{Cite journal\|last=Drozdowski\|first=Maciej\|date=2009\|title=Scheduling for Parallel Processing\|journal=Computer Communications and Networks\|language=en-gb\|doi=10.1007/978-1-84882-310-5\|isbn=978-1-84882-309-9\|issn=1617-7975}}</ref> denote this problem by <math> P\|size_j\|C_{\max} </math> in the [[Notation for theoretic scheduling problems\|three-field notation]] introduced by Graham et al.<ref name="initial specification">{{cite conference\|last1=Graham\|first1=R. L.\|last2=Lawler\|first2=E. L.\|last3=Lenstra\|first3=J.K.\|last4=Rinnooy Kan\|first4=A.H.G.\|year=1979\|title=Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey\|url=http://mat.uab.es/~alseda/MasterOpt/79_03_scheduling_survey.pdf\|publisher=Elsevier\|pages=(5) 287–326\|book-title=Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium}}</ref> '''P''' means that there are several identical machines running in parallel; ''size<sub>j</sub>'' means that each job has a size parameter; ''C''<sub>max</sub> means that the goal is to minimize the maximum completion time. Some authors use <math> P\|m_j\|C_{\max} </math> instead.'''<ref name="Johannes" />''' Note that the problem of [[parallel-machines scheduling]] is a special case of parallel-task scheduling where <math> size_j=1 </math> for all ''j'', that is, each job should run on a single machine.

	The origins of this problem formulation can be traced back to 1960.<ref>{{Cite journal\|last=Codd\|first=E. F.\|date=1960-06-01\|title=Multiprogram scheduling\|journal=Communications of the ACM\|language=EN\|volume=3\|issue=6\|pages=347–350\|doi=10.1145/367297.367317\|s2cid=14701351}}</ref> For this problem, there exists no polynomial time approximation algorithm with a ratio smaller than <math>3/2</math> unless <math>P=NP</math>.{{Citation needed\|date=June 2021}}		The origins of this problem formulation can be traced back to 1960.<ref>{{Cite journal\|last=Codd\|first=E. F.\|date=1960-06-01\|title=Multiprogram scheduling\|journal=Communications of the ACM\|language=EN\|volume=3\|issue=6\|pages=347–350\|doi=10.1145/367297.367317\|s2cid=14701351}}</ref> For this problem, there exists no polynomial time approximation algorithm with a ratio smaller than <math>3/2</math> unless <math>P=NP</math>.{{Citation needed\|date=June 2021}}

Citation bot: Alter: template type. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_webform 2136/3850

2022-07-31T06:58:51Z

Alter: template type. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_webform 2136/3850

← Previous revision		Revision as of 06:58, 31 July 2022
Line 52:		Line 52:

	Given an instance of the parallel task scheduling problem, the optimal makespan can differ depending on the constraint to the contiguity of the machines. If the jobs can be scheduled on non-contiguous machines, the optimal makespan can be smaller than in the case that they have to be scheduled on contiguous ones.		Given an instance of the parallel task scheduling problem, the optimal makespan can differ depending on the constraint to the contiguity of the machines. If the jobs can be scheduled on non-contiguous machines, the optimal makespan can be smaller than in the case that they have to be scheduled on contiguous ones.
	The difference between contiguous and non-contiguous schedules has been first demonstrated in 1992<ref>{{Cite ~~document~~\|title=Approximate algorithms scheduling parallelizable tasks {{!}} Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures\|language=EN\|doi=10.1145/140901.141909\|s2cid=15607549}}</ref> on an instance with <math>n=8</math> tasks, <math>m=23</math> processors, <math>C^{nc}_{\max}=17</math>, and <math>C^c_{\max}=18</math>.		The difference between contiguous and non-contiguous schedules has been first demonstrated in 1992<ref>{{Cite journal\|title=Approximate algorithms scheduling parallelizable tasks {{!}} Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures\|language=EN\|doi=10.1145/140901.141909\|s2cid=15607549}}</ref> on an instance with <math>n=8</math> tasks, <math>m=23</math> processors, <math>C^{nc}_{\max}=17</math>, and <math>C^c_{\max}=18</math>.
	Błądek et al.<ref name="contiguousVSnoncontiguous">{{cite journal\|last1=Błądek\|first1=Iwo\|last2=Drozdowski\|first2=Maciej\|last3=Guinand\|first3=Frédéric\|last4=Schepler\|first4=Xavier\|date=1 October 2015\|title=On contiguous and non-contiguous parallel task scheduling\|journal=Journal of Scheduling\|language=en\|volume=18\|issue=5\|pages=487–495\|doi=10.1007/s10951-015-0427-z\|issn=1099-1425\|doi-access=free}}</ref> studied these so-called c/nc-differences and proved the following points:		Błądek et al.<ref name="contiguousVSnoncontiguous">{{cite journal\|last1=Błądek\|first1=Iwo\|last2=Drozdowski\|first2=Maciej\|last3=Guinand\|first3=Frédéric\|last4=Schepler\|first4=Xavier\|date=1 October 2015\|title=On contiguous and non-contiguous parallel task scheduling\|journal=Journal of Scheduling\|language=en\|volume=18\|issue=5\|pages=487–495\|doi=10.1007/s10951-015-0427-z\|issn=1099-1425\|doi-access=free}}</ref> studied these so-called c/nc-differences and proved the following points:

OAbot: Open access bot: doi added to citation with #oabot.

2021-07-05T14:53:26Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 14:53, 5 July 2021
Line 42:		Line 42:

	The list scheduling algorithm by Garey and Graham<ref>{{cite journal \|last1=Garey \|first1=M. R. \|last2=Graham \|first2=R. L. \|title=Bounds for Multiprocessor Scheduling with Resource Constraints \|journal=SIAM Journal on Computing \|date=1 June 1975 \|volume=4 \|issue=2 \|pages=187–200 \|doi=10.1137/0204015 \|issn=0097-5397\|doi-access=free }}</ref> has an absolute ratio <math>2</math>, as pointed out by Turek et al.<ref>{{cite journal \|last1=Turek \|first1=John \|last2=Wolf \|first2=Joel L. \|last3=Yu \|first3=Philip S. \|title=Approximate algorithms scheduling parallelizable tasks {{!}} Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures \|website=dl.acm.org \|doi=10.1145/140901.141909 \|s2cid=15607549 \|language=EN}}</ref> and Ludwig and Tiwari.<ref>{{cite journal \|last1=Ludwig \|first1=Walter \|last2=Tiwari \|first2=Prasoon \|title=Scheduling malleable and nonmalleable parallel tasks {{!}} Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms \|journal=Fifth Annual {ACM-SIAM} Symposium on Discrete Algorithms (SODA) \|date=1994 \|pages=167–176 \|url=http://dl.acm.org/citation.cfm?id=314464.314491 \|language=EN}}</ref>		The list scheduling algorithm by Garey and Graham<ref>{{cite journal \|last1=Garey \|first1=M. R. \|last2=Graham \|first2=R. L. \|title=Bounds for Multiprocessor Scheduling with Resource Constraints \|journal=SIAM Journal on Computing \|date=1 June 1975 \|volume=4 \|issue=2 \|pages=187–200 \|doi=10.1137/0204015 \|issn=0097-5397\|doi-access=free }}</ref> has an absolute ratio <math>2</math>, as pointed out by Turek et al.<ref>{{cite journal \|last1=Turek \|first1=John \|last2=Wolf \|first2=Joel L. \|last3=Yu \|first3=Philip S. \|title=Approximate algorithms scheduling parallelizable tasks {{!}} Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures \|website=dl.acm.org \|doi=10.1145/140901.141909 \|s2cid=15607549 \|language=EN}}</ref> and Ludwig and Tiwari.<ref>{{cite journal \|last1=Ludwig \|first1=Walter \|last2=Tiwari \|first2=Prasoon \|title=Scheduling malleable and nonmalleable parallel tasks {{!}} Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms \|journal=Fifth Annual {ACM-SIAM} Symposium on Discrete Algorithms (SODA) \|date=1994 \|pages=167–176 \|url=http://dl.acm.org/citation.cfm?id=314464.314491 \|language=EN}}</ref>
	Feldmann, Sgall and Teng<ref>{{cite journal \|last1=Feldmann \|first1=Anja \|last2=Sgall \|first2=Jiří \|last3=Teng \|first3=Shang-Hua \|title=Dynamic scheduling on parallel machines \|journal=Theoretical Computer Science \|date=1 August 1994 \|volume=130 \|issue=1 \|pages=49–72 \|doi=10.1016/0304-3975(94)90152-X \|language=en \|issn=0304-3975}}</ref> observed that the length of a non-preemptive schedule produced by the list scheduling algorithm is actually at most <math>(2-1/m)</math> times the optimum preemptive makespan.		Feldmann, Sgall and Teng<ref>{{cite journal \|last1=Feldmann \|first1=Anja \|last2=Sgall \|first2=Jiří \|last3=Teng \|first3=Shang-Hua \|title=Dynamic scheduling on parallel machines \|journal=Theoretical Computer Science \|date=1 August 1994 \|volume=130 \|issue=1 \|pages=49–72 \|doi=10.1016/0304-3975(94)90152-X \|language=en \|issn=0304-3975\|doi-access=free }}</ref> observed that the length of a non-preemptive schedule produced by the list scheduling algorithm is actually at most <math>(2-1/m)</math> times the optimum preemptive makespan.
	A polynomial-time approximation scheme (PTAS) for the case when the number <math>m</math> of processors is constant, denoted by <math>Pm\|size_j\|C_{\max}</math>, was presented by Amoura et al.<ref>{{cite journal \|last1=Amoura \|first1=Abdel Krim \|last2=Bampis \|first2=Evripidis \|last3=Kenyon \|first3=Claire \|last4=Manoussakis \|first4=Yannis \|title=Scheduling Independent Multiprocessor Tasks \|journal=Algorithmica \|date=1 February 2002 \|volume=32 \|issue=2 \|pages=247–261 \|doi=10.1007/s00453-001-0076-9 \|s2cid=17256951 \|language=en \|issn=1432-0541}}</ref> and Jansen et al.<ref>{{cite journal \|last1=Jansen \|first1=Klaus \|last2=Porkolab \|first2=Lorant \|title=Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks \|journal=Algorithmica \|date=1 March 2002 \|volume=32 \|issue=3 \|pages=507–520 \|doi=10.1007/s00453-001-0085-8 \|language=en \|issn=1432-0541\|hdl=11858/00-001M-0000-0014-7B6C-D \|s2cid=2019475 \|hdl-access=free }}</ref>		A polynomial-time approximation scheme (PTAS) for the case when the number <math>m</math> of processors is constant, denoted by <math>Pm\|size_j\|C_{\max}</math>, was presented by Amoura et al.<ref>{{cite journal \|last1=Amoura \|first1=Abdel Krim \|last2=Bampis \|first2=Evripidis \|last3=Kenyon \|first3=Claire \|last4=Manoussakis \|first4=Yannis \|title=Scheduling Independent Multiprocessor Tasks \|journal=Algorithmica \|date=1 February 2002 \|volume=32 \|issue=2 \|pages=247–261 \|doi=10.1007/s00453-001-0076-9 \|s2cid=17256951 \|language=en \|issn=1432-0541}}</ref> and Jansen et al.<ref>{{cite journal \|last1=Jansen \|first1=Klaus \|last2=Porkolab \|first2=Lorant \|title=Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks \|journal=Algorithmica \|date=1 March 2002 \|volume=32 \|issue=3 \|pages=507–520 \|doi=10.1007/s00453-001-0085-8 \|language=en \|issn=1432-0541\|hdl=11858/00-001M-0000-0014-7B6C-D \|s2cid=2019475 \|hdl-access=free }}</ref>
	Later, Jansen and Thöle <ref name="PPTAS" /> found a PTAS for the case where the number of processors is polynomially bounded in the number of jobs.		Later, Jansen and Thöle <ref name="PPTAS" /> found a PTAS for the case where the number of processors is polynomially bounded in the number of jobs.

← Previous revision		Revision as of 18:54, 8 January 2023
Line 1:		Line 1:
	'''Parallel task scheduling''' (also called '''parallel job scheduling<ref name="Johannes" /><ref name="PPTAS" />''' or '''parallel processing scheduling<ref name=":0" />''') is an [[optimization problem]] in [[computer science]] and [[Operations Research\|operations research]]. It is a variant of [[optimal job scheduling]]. In a general job scheduling problem, we are given ''n'' jobs ''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' of varying processing times, which need to be scheduled on ''m'' machines while trying to minimize the [[makespan]] - the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as ''parallel-task scheduling'', all machines are identical. Each job ''j'' has a ''length'' parameter ''p<sub>j</sub>'' and a ''size'' parameter ''q''<sub>j</sub>, and it must run for exactly ''p<sub>j</sub>'' time-steps on exactly ''q''<sub>j</sub> machines in ''parallel''.		'''Parallel task scheduling''' (also called '''parallel job scheduling<ref name="Johannes" /><ref name="PPTAS" />''' or '''parallel processing scheduling<ref name=":0" />''') is an [[optimization problem]] in [[computer science]] and [[Operations Research\|operations research]]. It is a variant of [[optimal job scheduling]]. In a general job scheduling problem, we are given ''n'' jobs ''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' of varying processing times, which need to be scheduled on ''m'' machines while trying to minimize the [[makespan]] - the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as ''parallel-task scheduling'', all machines are identical. Each job ''j'' has a ''length'' parameter ''p<sub>j</sub>'' and a ''size'' parameter ''q''<sub>j</sub>, and it must run for exactly ''p<sub>j</sub>'' time-steps on exactly ''q''<sub>j</sub> machines in ''parallel''.

	Veltman et al.<ref>{{Cite journal\|last1=Veltman\|first1=B\|last2=Lageweg\|first2=B. J\|last3=Lenstra\|first3=J. K\|date=1990-12-01\|title=Multiprocessor scheduling with communication delays\|journal=Parallel Computing\|language=en\|volume=16\|issue=2\|pages=173–182\|doi=10.1016/0167-8191(90)90056-F\|issn=0167-8191\|url=https://ir.cwi.nl/pub/5713}}</ref> and Drozdowski<ref name=":0">{{Cite journal\|last=Drozdowski\|first=Maciej\|date=2009\|title=Scheduling for Parallel Processing\|journal=Computer Communications and Networks\|language=en-gb\|doi=10.1007/978-1-84882-310-5\|isbn=978-1-84882-309-9\|issn=1617-7975}}</ref> denote this problem by <math> P\|size_j\|C_{\max} </math> in the [[Notation for theoretic scheduling problems\|three-field notation]] introduced by Graham et al.<ref name="initial specification">{{cite conference\|last1=Graham\|first1=R. L.\|last2=Lawler\|first2=E. L.\|last3=Lenstra\|first3=J.K.\|last4=Rinnooy Kan\|first4=A.H.G.\|year=1979\|title=Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey\|url=http://mat.uab.es/~alseda/MasterOpt/79_03_scheduling_survey.pdf\|publisher=Elsevier\|pages=(5) 287–326\|book-title=Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium}}</ref> '''P''' means that there are several identical machines running in parallel; ''size<sub>j</sub>'' means that each job has a size parameter; ''C''<sub>max</sub> means that the goal is to minimize the maximum completion time. Some authors use <math> P\|m_j\|C_{\max} </math> instead.'''<ref name="Johannes" />'''		Veltman et al.<ref>{{Cite journal\|last1=Veltman\|first1=B\|last2=Lageweg\|first2=B. J\|last3=Lenstra\|first3=J. K\|date=1990-12-01\|title=Multiprocessor scheduling with communication delays\|journal=Parallel Computing\|language=en\|volume=16\|issue=2\|pages=173–182\|doi=10.1016/0167-8191(90)90056-F\|issn=0167-8191\|url=https://ir.cwi.nl/pub/5713}}</ref> and Drozdowski<ref name=":0">{{Cite journal\|last=Drozdowski\|first=Maciej\|date=2009\|title=Scheduling for Parallel Processing\|journal=Computer Communications and Networks\|language=en-gb\|doi=10.1007/978-1-84882-310-5\|isbn=978-1-84882-309-9\|issn=1617-7975}}</ref> denote this problem by <math> P\|size_j\|C_{\max} </math> in the [[Notation for theoretic scheduling problems\|three-field notation]] introduced by Graham et al.<ref name="initial specification">{{cite conference\|last1=Graham\|first1=R. L.\|last2=Lawler\|first2=E. L.\|last3=Lenstra\|first3=J.K.\|last4=Rinnooy Kan\|first4=A.H.G.\|year=1979\|title=Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey\|url=http://mat.uab.es/~alseda/MasterOpt/79_03_scheduling_survey.pdf\|publisher=Elsevier\|pages=(5) 287–326\|book-title=Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium}}</ref> '''P''' means that there are several identical machines running in parallel; ''size<sub>j</sub>'' means that each job has a size parameter; ''C''<sub>max</sub> means that the goal is to minimize the maximum completion time. Some authors use <math> P\|m_j\|C_{\max} </math> instead.'''<ref name="Johannes" />''' Note that the problem of [[parallel-machines scheduling]] is a special case of parallel-task scheduling where <math> size_j=1 </math> for all ''j'', that is, each job should run on a single machine.

	The origins of this problem formulation can be traced back to 1960.<ref>{{Cite journal\|last=Codd\|first=E. F.\|date=1960-06-01\|title=Multiprogram scheduling\|journal=Communications of the ACM\|language=EN\|volume=3\|issue=6\|pages=347–350\|doi=10.1145/367297.367317\|s2cid=14701351}}</ref> For this problem, there exists no polynomial time approximation algorithm with a ratio smaller than <math>3/2</math> unless <math>P=NP</math>.{{Citation needed\|date=June 2021}}		The origins of this problem formulation can be traced back to 1960.<ref>{{Cite journal\|last=Codd\|first=E. F.\|date=1960-06-01\|title=Multiprogram scheduling\|journal=Communications of the ACM\|language=EN\|volume=3\|issue=6\|pages=347–350\|doi=10.1145/367297.367317\|s2cid=14701351}}</ref> For this problem, there exists no polynomial time approximation algorithm with a ratio smaller than <math>3/2</math> unless <math>P=NP</math>.{{Citation needed\|date=June 2021}}