Journal articles: 'Job parallèle'

1

Brecht, Timothy, Xiaotie Deng, and Nian Gu. "Competitive Dynamic Multiprocessor Allocation for Parallel Applications." Parallel Processing Letters 07, no. 01 (March 1997): 89–100. http://dx.doi.org/10.1142/s0129626497000115.

Full text

Abstract:

We study dynamic multiprocessor allocation policies for parallel jobs, which allow the preemption and reallocation of processors to take place at any time. The objective is to minimize the completion time of the last job to finish executing (the makespan). We characterize a parallel job using two parameter. The job's parallelism, Pi, which is the number of tasks being executed in parallel by a job, and its execution time, li, when Pi processors are allocated to the job. The only information available to the scheduler is the parallelism of jobs. The job execution time is not known to the scheduler until the job's execution is completed. We apply the approach of competitive analysis to compare preemptive scheduling policies, and are interested in determining which policy achieves the best competitive ratio (i.e., is within the smallest constant factor of optimal). We devise an optimal competitive scheduling policy for scheduling two parallel jobs on P processors. Then, we apply the method to schedule N parallel jobs on P processors. Finally we extend our work to incorporate jobs for which the number of parallel tasks changes during execution (i.e., jobs with multiple phases of parallelism).

APA, Harvard, Vancouver, ISO, and other styles

2

Weng, Wentao, and Weina Wang. "Achieving Zero Asymptotic Queueing Delay for Parallel Jobs." ACM SIGMETRICS Performance Evaluation Review 49, no. 1 (June 22, 2022): 25–26. http://dx.doi.org/10.1145/3543516.3456268.

Full text

Abstract:

Zero queueing delay is highly desirable in large-scale computing systems. Existing work has shown that it can be asymptotically achieved by using the celebrated Power-of-d-choices (Pod) policy with a probe overhead d = Ω(log N/1-λ), and it is impossible when d = O(1/1-λ), where N is the number of servers and λ is the load of the system. However, these results are based on the model where each job is an indivisible unit, which does not capture the parallel structure of jobs in today's predominant parallel computing paradigm. This paper considers a model where each job consists of a batch of parallel tasks. Under this model, we propose a new notion of zero (asymptotic) queueing delay that requires the job delay under a policy to approach the job delay given by the max of its tasks' service times, i.e., the job delay assuming its tasks entered service right upon arrival. This notion quantifies the effect of queueing on a job level for jobs consisting of multiple tasks, and thus deviates from the conventional zero queueing delay for single-task jobs in the literature. We show that zero queueing delay for parallel jobs can be achieved using the batch-filling policy (a variant of the celebrated Pod policy) with a probe overhead d = Ω(1/(1-λ)log k) in the sub-Halfin-Whitt heavy-traffic regime, where k is the number of tasks in each job and k properly scales with N (the number of servers). This result demonstrates that for parallel jobs, zero queueing delay can be achieved with a smaller probe overhead. We also establish an impossibility result: we show that zero queueing delay cannot be achieved if d = (o(log N/log k)). Simulation results are provided to demonstrate the consistency between numerical results and theoretical results under reasonable settings, and to investigate gaps in the theoretical analysis.

APA, Harvard, Vancouver, ISO, and other styles

3

Xu, Susan H. "On a job resequencing issue in parallel processor stochastic scheduling." Advances in Applied Probability 24, no. 4 (December 1992): 915–33. http://dx.doi.org/10.2307/1427719.

Full text

Abstract:

In flexible assembly systems, it is often necessary to coordinate jobs and materials so that specific jobs are matched with specific materials. This requires that jobs depart from upstream parallel workstations in some predetermined order. One way to satisfy this requirement is to temporarily hold the serviced jobs getting out of order at a resequencing buffer and to release them to downstream workstations as soon as all their predecessors are serviced. In this paper we consider the problem of scheduling a fixed number of non-preemptive jobs on two IHR non-identical processors with the resequencing requirement. We prove that the individually optimal policy, in which each job minimizes its own expected departure time subject to the constraint that available processors are offered to jobs in their departure order, is of a threshold type. The policy is independent of job weights and the jobs residing at the resequencing buffer and possesses the monotonicity property which states that a job will never utilize a processor in the future once it has declined the processor. Most importantly, we prove that the individually optimal policy has the stability property; namely: if at any time a job deviated from the individually optimal policy, then the departure time of every job, including its own, would be prolonged. As a direct consequence of this property, the individually optimal policy is socially optimal in the sense that it minimizes the expected total weighted departure time of the system as a whole. We identify situations under which the individually optimal policy also minimizes the expected makespan of the system.

APA, Harvard, Vancouver, ISO, and other styles

4

Xu, Susan H. "On a job resequencing issue in parallel processor stochastic scheduling." Advances in Applied Probability 24, no. 04 (December 1992): 915–33. http://dx.doi.org/10.1017/s0001867800025015.

Full text

Abstract:

In flexible assembly systems, it is often necessary to coordinate jobs and materials so that specific jobs are matched with specific materials. This requires that jobs depart from upstream parallel workstations in some predetermined order. One way to satisfy this requirement is to temporarily hold the serviced jobs getting out of order at a resequencing buffer and to release them to downstream workstations as soon as all their predecessors are serviced. In this paper we consider the problem of scheduling a fixed number of non-preemptive jobs on two IHR non-identical processors with the resequencing requirement. We prove that the individually optimal policy, in which each job minimizes its own expected departure time subject to the constraint that available processors are offered to jobs in their departure order, is of a threshold type. The policy is independent of job weights and the jobs residing at the resequencing buffer and possesses the monotonicity property which states that a job will never utilize a processor in the future once it has declined the processor. Most importantly, we prove that the individually optimal policy has the stability property; namely: if at any time a job deviated from the individually optimal policy, then the departure time of every job, including its own, would be prolonged. As a direct consequence of this property, the individually optimal policy is socially optimal in the sense that it minimizes the expected total weighted departure time of the system as a whole. We identify situations under which the individually optimal policy also minimizes the expected makespan of the system.

APA, Harvard, Vancouver, ISO, and other styles

5

Kumar, P. R., and J. Walrand. "Individually optimal routing in parallel systems." Journal of Applied Probability 22, no. 4 (December 1985): 989–95. http://dx.doi.org/10.2307/3213970.

Full text

Abstract:

Jobs arrive at a buffer from which there are several parallel routes to a destination. A socially optimal policy is one which minimizes the average delay of all jobs, whereas an individually optimal policy is one which, for each job, minimizes its own delay, with route preference given to jobs at the head of the buffer. If there is a socially optimal policy for a system with no arrivals, which can be implemented by each job following a policy γ in such a way that no job ever utilizes a previously declined route, then we show that such a γ is an individually optimal policy for each job. Moreover γ continues to be individually optimal even if the system has an arbitrary arrival process, subject only to the restriction that past arrivals are independent of future route-traversal times. Thus, γ is an individually optimal policy which is insensitive to the nature of the arrival process. In the particular case where the times to traverse the routes are exponentially distributed with a possibly different mean time for each of the parallel routes, then such an insensitive individually optimal policy does in fact exist and is moreover trivially determined by certain threshold numbers. A conjecture is also made about more general situations where such individually optimal policies exist.

APA, Harvard, Vancouver, ISO, and other styles

6

Kumar, P. R., and J. Walrand. "Individually optimal routing in parallel systems." Journal of Applied Probability 22, no. 04 (December 1985): 989–95. http://dx.doi.org/10.1017/s0021900200108265.

Full text

Abstract:

Jobs arrive at a buffer from which there are several parallel routes to a destination. A socially optimal policy is one which minimizes the average delay of all jobs, whereas an individually optimal policy is one which, for each job, minimizes its own delay, with route preference given to jobs at the head of the buffer. If there is a socially optimal policy for a system with no arrivals, which can be implemented by each job following a policy γ in such a way that no job ever utilizes a previously declined route, then we show that such a γ is an individually optimal policy for each job. Moreover γ continues to be individually optimal even if the system has an arbitrary arrival process, subject only to the restriction that past arrivals are independent of future route-traversal times. Thus, γ is an individually optimal policy which is insensitive to the nature of the arrival process. In the particular case where the times to traverse the routes are exponentially distributed with a possibly different mean time for each of the parallel routes, then such an insensitive individually optimal policy does in fact exist and is moreover trivially determined by certain threshold numbers. A conjecture is also made about more general situations where such individually optimal policies exist.

APA, Harvard, Vancouver, ISO, and other styles

7

Zheng, Feifeng, Ming Liu, Chengbin Chu, and Yinfeng Xu. "Online Parallel Machine Scheduling to Maximize the Number of Early Jobs." Mathematical Problems in Engineering 2012 (2012): 1–7. http://dx.doi.org/10.1155/2012/939717.

Full text

Abstract:

We study a maximization problem: online scheduling onmidentical machines to maximize the number of early jobs. The problem is online in the sense that all jobs arrive over time. Each job's characteristics, such as processing time and due date, become known at its arrival time. We consider thepreemption-restart model, in which preemption is allowed, while once a job is restarted, it loses all the progress that has been made on this job so far. If in some schedule a job is completed before or at its due date, then it is calledearly(oron time). The objective is to maximize the number of early jobs. Formidentical machines, we prove an upper bound1-(1/2m)of competitive ratio and show thatECT(earliest completion time) algorithm is1/2-competitive.

APA, Harvard, Vancouver, ISO, and other styles

8

Shim, Sang Oh, and Seong Woo Choi. "Scheduling Jobs on Dedicated Parallel Machines." Applied Mechanics and Materials 433-435 (October 2013): 2363–66. http://dx.doi.org/10.4028/www.scientific.net/amm.433-435.2363.

Full text

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.

APA, Harvard, Vancouver, ISO, and other styles

9

Liu, Ming, Feifeng Zheng, Zhanguo Zhu, and Chengbin Chu. "Optimal Semi-Online Algorithm for Scheduling on Two Parallel Batch Processing Machines." Asia-Pacific Journal of Operational Research 31, no. 05 (October 2014): 1450038. http://dx.doi.org/10.1142/s0217595914500389.

Full text

Abstract:

Batch processing machine scheduling in uncertain environment attracts more and more attention in the last decade. This paper deals with semi-online scheduling on two parallel batch processing machines with non-decreasing processing time of job. Jobs arrive over time in the online paradigm, and the processing time of any batch is equal to the length of the last arrival job in the batch. We study the unbounded model where each processing batch may contain an unlimited number of jobs, and the objective is to minimize the makespan. Given any job Jj together with its following job Jj+1, it is assumed that their processing times satisfy pj+1 ≥ αpj where α ≥ 1 is a constant. That is, jobs arrive in a non-decreasing order of processing times. We mainly propose an optimal ϕ-competitive online algorithm where ϕ ≥ 1 is a solution of equation ϕ3 + (α-1)ϕ2 + (α2 - α - 1)ϕ - α2 = 0.

APA, Harvard, Vancouver, ISO, and other styles

10

Luo, Cheng Xin. "An FPTAS for Uniform Parallel-Machine Scheduling Problem with Deteriorating Jobs and Rejection." Applied Mechanics and Materials 433-435 (October 2013): 2335–38. http://dx.doi.org/10.4028/www.scientific.net/amm.433-435.2335.

Full text

Abstract:

This paper studies uniform parallel-machine scheduling problem with deteriorating jobs and rejection. The processing time of each job is a linear nondecreasing function of its starting time. A job can be rejected by paying a penalty cost. The objective is to minimize the sum of the total load of the accepted jobs on all machines and the total rejection penalties of the rejected jobs. We propose a fully polynomial-time approximation scheme (FPTAS) for this problem.

APA, Harvard, Vancouver, ISO, and other styles

11

Liu, Peng Fei, and Shou Bin Dong. "Multi-Objective Scheduling for Parallel Jobs on Grid." Key Engineering Materials 439-440 (June 2010): 1281–86. http://dx.doi.org/10.4028/www.scientific.net/kem.439-440.1281.

Full text

Abstract:

Focused on the complexity of the parallel job scheduling on heterogeneous Grid, the paper proposes a multi-objective optimization based scheduling algorithm. The algorithm first splits the parallel job up into a series of independent processes with constraints, and then adopts particles to represent the mapping of job-resource. Multi-objective PSO is employed to simultaneously optimize the scheduling objectives of throughput and average turnaround time. Experimental result indicates that the proposed approach is effective while dealing with large scale parallel jobs scheduling on heterogeneous Grid and outperforms other conventional algorithms.

APA, Harvard, Vancouver, ISO, and other styles

12

Cheng, Bihui, and Wencheng Wang. "A Combinatorial Approximation Algorithm for the Vector Scheduling with Submodular Penalties on Parallel Machines." Journal of Mathematics 2023 (November 29, 2023): 1–8. http://dx.doi.org/10.1155/2023/8886388.

Full text

Abstract:

In this paper, we focus on solving the vector scheduling problem with submodular penalties on parallel machines. We are given n jobs and m parallel machines, where each job is associated with a d -dimensional vector. Each job can either be rejected, incurring a rejection penalty, or accepted and processed on one of the m parallel machines. The objective is to minimize the sum of the maximum load overall dimensions of the total vector for all accepted jobs, along with the total penalty for rejected jobs. The penalty is determined by a submodular function. Our main work is to design a 2 − 1 / m min r , d -approximation algorithm to solve this problem. Here, r denotes the maximum ratio of the maximum load to the minimum load on the d -dimensional vectors among all jobs.

APA, Harvard, Vancouver, ISO, and other styles

13

Liu, Qijia, and Jinjiang Yuan. "Online Scheduling of Incompatible Family Jobs with Equal Length on an Unbounded Parallel-Batch Machine with Job Delivery." Asia-Pacific Journal of Operational Research 35, no. 04 (August 2018): 1850026. http://dx.doi.org/10.1142/s0217595918500264.

Full text

Abstract:

In this paper, we consider the online scheduling of incompatible family jobs with equal length on an unbounded parallel-batch machine with job delivery. The jobs arrive online over time and belong to [Formula: see text] incompatible job families, where [Formula: see text] is known in advance. The jobs are first processed in batches on an unbounded parallel-batch machine and then the completed jobs are delivered in batches by a vehicle with infinite capacity to their customers. The jobs from distinct families cannot be processed and delivered in the same batch. The objective is to minimize the maximum delivery completion time of the jobs. For this problem, we present an online algorithm with the best competitive ratio of [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

14

Ibrahim, Fahim Mohammed, Hanan Ali Chachan, and Ali A. D. Al-Zuky. "Theoretical Approaches Parallel Identical Machines with Multi-Objective Functions." Al-Mustansiriyah Journal of Science 33, no. 3 (September 25, 2022): 54–59. http://dx.doi.org/10.23851/mjs.v33i3.1149.

Full text

Abstract:

In this study, we propose multi-objective functions which consist of the sum of completion time, tardiness time and earliness time where Ci denoted the completion time of job (i), Ti=max{Ci-di,0}, denotes the tardiness of job (i), Ei=max{di-Ci,0} be denoted the earliness of job (i).This problem is defined by // In this paper, we will present some theoretical analysis discussion, and prove when we have a problem with scheduling n jobs on two identical parallel machines (IPMSP).

APA, Harvard, Vancouver, ISO, and other styles

15

Pinedo, Michael, and Zvi Schechner. "Inequalities and bounds for the scheduling of stochastic jobs on parallel machines." Journal of Applied Probability 22, no. 3 (September 1985): 739–44. http://dx.doi.org/10.2307/3213879.

Full text

Abstract:

Consider n jobs and m machines. The m machines are identical and set up in parallel. All n jobs are available at t = 0 and each job has to be processed on one of the machines; any one can do. The processing time of job j is Xj, a random variable with distribution Fj. The sequence in which the jobs start with their processing is predetermined and preemptions are not allowed. We investigate the effect of the variability of the processing times on the expected makespan and the expected time to first idleness. Bounds are presented for these quantities in case the distributions of the processing times of the jobs are new better (worse) than used.

APA, Harvard, Vancouver, ISO, and other styles

16

Pinedo, Michael, and Zvi Schechner. "Inequalities and bounds for the scheduling of stochastic jobs on parallel machines." Journal of Applied Probability 22, no. 03 (September 1985): 739–44. http://dx.doi.org/10.1017/s002190020002951x.

Full text

Abstract:

Consider n jobs and m machines. The m machines are identical and set up in parallel. All n jobs are available at t = 0 and each job has to be processed on one of the machines; any one can do. The processing time of job j is Xj , a random variable with distribution Fj. The sequence in which the jobs start with their processing is predetermined and preemptions are not allowed. We investigate the effect of the variability of the processing times on the expected makespan and the expected time to first idleness. Bounds are presented for these quantities in case the distributions of the processing times of the jobs are new better (worse) than used.

APA, Harvard, Vancouver, ISO, and other styles

17

ZAJÍČEK, ONDŘEJ. "A NOTE ON SCHEDULING PARALLEL UNIT JOBS ON HYPERCUBES." International Journal of Foundations of Computer Science 20, no. 02 (April 2009): 341–49. http://dx.doi.org/10.1142/s0129054109006590.

Full text

Abstract:

We study the problem of scheduling independent unit-time parallel jobs on hypercubes. A parallel job has to be scheduled between its release time and deadline on a subcube of processors. The objective is to maximize the number of early jobs. Jobs' intervals of feasibility have to be nested. We provide a polynomial time algorithm for the problem.

APA, Harvard, Vancouver, ISO, and other styles

18

Jin, Miaomiao, Xiaoxia Liu, and Wenchang Luo. "Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection." Mathematics 8, no. 2 (February 16, 2020): 258. http://dx.doi.org/10.3390/math8020258.

Full text

Abstract:

We investigate the single-machine parallel-batch scheduling problem with nonidentical job sizes and rejection. In this problem, a set of jobs with different processing times and nonidentical sizes is given to be possibly processed on a parallel-batch processing machine. Each job is either accepted and then processed on the machine or rejected by paying its rejection penalty. Preemption is not allowed. Our task is to choose the accepted jobs and schedule them as batches on the machine to minimize the makespan of the accepted jobs plus the total rejection penalty of the rejected jobs. We provide an integer programming formulation to exactly solve our problem. Then, we propose three fast heuristic algorithms to solve the problem and evaluate their performances by using a small numerical example.

APA, Harvard, Vancouver, ISO, and other styles

19

Zou, Juan, and Cuixia Miao. "Parallel Batch Scheduling of Deteriorating Jobs with Release Dates and Rejection." Scientific World Journal 2014 (2014): 1–7. http://dx.doi.org/10.1155/2014/270942.

Full text

Abstract:

We consider the unbounded parallel batch scheduling with deterioration, release dates, and rejection. Each job is either accepted and processed on a single batching machine, or rejected by paying penalties. The processing time of a job is a simple linear increasing function of its starting time. The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejected jobs. First, we show that the problem is NP-hard in the ordinary sense. Then, we present two pseudopolynomial time algorithms and a fully polynomial-time approximation scheme to solve this problem. Furthermore, we provide an optimalO(nlog⁡n)time algorithm for the case where jobs have identical release dates.

APA, Harvard, Vancouver, ISO, and other styles

20

LIN, LIN, YIXUN LIN, XIANWEI ZHOU, and RUYAN FU. "PARALLEL MACHINE SCHEDULING WITH A SIMULTANEITY CONSTRAINT AND UNIT-LENGTH JOBS TO MINIMIZE THE MAKESPAN." Asia-Pacific Journal of Operational Research 27, no. 06 (December 2010): 669–76. http://dx.doi.org/10.1142/s0217595910002934.

Full text

Abstract:

In this paper, we consider the parallel machine scheduling with a simultaneity constraint and unit-length jobs. The problem can be described as follows. There are given m parallel machines and a graph G, whose vertices represent jobs. Simultaneity constraint means that we can process a vertex job v if and only if there exists at least dG(v) idle machines, where dG(v) is the degree of vertex v in graph G. Once a vertex job is completed, we delete the vertex and its incident edges from the graph. The number of machines that a vertex job needing depends on its degree in current graph. Changes of graph result in changes of vertex degree. Here, we consider a special case that all jobs in the original graph are unit-length. Let pv denote the processing time of vertex job v, we define pv = 0 if d(v) = 0, and pv = 1, otherwise. The objective is to minimize the time by which each vertex job is completed, i.e., the time by which the graph becomes an empty graph. We show that this problem is strongly NP-hard and provide a [Formula: see text]-approximation algorithm.

APA, Harvard, Vancouver, ISO, and other styles

21

Bambos, Nicholas, and Shou C. Chen. "Optimality Aspects of Greedy Schemes in Parallel Processing of Random Graph-Structured Jobs." Probability in the Engineering and Informational Sciences 8, no. 2 (April 1994): 229–43. http://dx.doi.org/10.1017/s0269964800003375.

Full text

Abstract:

Parallel processing systems with jobs structured as random graphs, where the nodes correspond to executable tasks and the directed edges to precedence constraints, are studied from a queueing theoretic point of view under general stationarity assumptions on the job flows. Jobs need to have their tasks processed non-preemptively by a set of uniform processors. Simple, natural greedy schemes of allocating processors to tasks are shown to asymptotically minimize the long-term average execution time per job. The stability condition for this queueing system is specified, and greedy allocation schemes are shown to stabilize the system under the maximum possible job arrival rate. Some recurrence properties of the system state are also established.

APA, Harvard, Vancouver, ISO, and other styles

22

Chang, Cheng-Shang, Xiuli Chao, Michael Pinedo, and Richard Weber. "On the optimality of LEPT and cµ rules for machines in parallel." Journal of Applied Probability 29, no. 3 (September 1992): 667–81. http://dx.doi.org/10.2307/3214903.

Full text

Abstract:

We consider scheduling problems with m machines in parallel and n jobs. The machines are subject to breakdown and repair. Jobs have exponentially distributed processing times and possibly random release dates. For cost functions that only depend on the set of uncompleted jobs at time t we provide necessary and sufficient conditions for the LEPT rule to minimize the expected cost at all t within the class of preemptive policies. This encompasses results that are known for makespan, and provides new results for the work remaining at time t. An application is that if the cµ rule has the same priority assignment as the LEPT rule then it minimizes the expected weighted number of jobs in the system for all t. Given appropriate conditions, we also show that the cµ rule minimizes the expected value of other objective functions, such as weighted sum of job completion times, weighted number of late jobs, or weighted sum of job tardinesses, when jobs have a common random due date.

APA, Harvard, Vancouver, ISO, and other styles

23

Chang, Cheng-Shang, Xiuli Chao, Michael Pinedo, and Richard Weber. "On the optimality of LEPT and cµ rules for machines in parallel." Journal of Applied Probability 29, no. 03 (September 1992): 667–81. http://dx.doi.org/10.1017/s0021900200043485.

Full text

Abstract:

We consider scheduling problems with m machines in parallel and n jobs. The machines are subject to breakdown and repair. Jobs have exponentially distributed processing times and possibly random release dates. For cost functions that only depend on the set of uncompleted jobs at time t we provide necessary and sufficient conditions for the LEPT rule to minimize the expected cost at all t within the class of preemptive policies. This encompasses results that are known for makespan, and provides new results for the work remaining at time t. An application is that if the cµ rule has the same priority assignment as the LEPT rule then it minimizes the expected weighted number of jobs in the system for all t. Given appropriate conditions, we also show that the cµ rule minimizes the expected value of other objective functions, such as weighted sum of job completion times, weighted number of late jobs, or weighted sum of job tardinesses, when jobs have a common random due date.

APA, Harvard, Vancouver, ISO, and other styles

24

Wang, Wencheng, and Xiaofei Liu. "A Combinatorial 2-Approximation Algorithm for the Parallel-Machine Scheduling with Release Times and Submodular Penalties." Mathematics 10, no. 1 (December 25, 2021): 61. http://dx.doi.org/10.3390/math10010061.

Full text

Abstract:

In this paper, we consider parallel-machine scheduling with release times and submodular penalties (P|rj,reject|Cmax+π(R)), in which each job can be accepted and processed on one of m identical parallel machines or rejected, but a penalty must paid if a job is rejected. Each job has a release time and a processing time, and the job can not be processed before its release time. The objective of P|rj,reject|Cmax+π(R) is to minimize the makespan of the accepted jobs plus the penalty of the rejected jobs, where the penalty is determined by a submodular function. This problem generalizes a multiprocessor scheduling problem with rejection, the parallel-machine scheduling with submodular penalties, and the single machine scheduling problem with release dates and submodular rejection penalties. In this paper, inspired by the primal-dual method, we present a combinatorial 2-approximation algorithm to P|rj,reject|Cmax+π(R). This ratio coincides with the best known ratio for the parallel-machine scheduling with submodular penalties and the single machine scheduling problem with release dates and submodular rejection penalties.

APA, Harvard, Vancouver, ISO, and other styles

25

DONG, J. M., X. S. WANG, L. L. WANG, and J. L. HU. "PARALLEL MACHINE SCHEDULING WITH JOB DELIVERY COORDINATION." ANZIAM Journal 58, no. 3-4 (April 2017): 306–13. http://dx.doi.org/10.1017/s1446181117000190.

Full text

Abstract:

We analyse a parallel (identical) machine scheduling problem with job delivery to a single customer. For this problem, each job needs to be processed on $m$ parallel machines non-pre-emptively and then transported to a customer by one vehicle with a limited physical capacity. The optimization goal is to minimize the makespan, the time at which all the jobs are processed and delivered and the vehicle returns to the machine. We present an approximation algorithm with a tight worst-case performance ratio of $7/3-1/m$ for the general case, $m\geq 3$.

APA, Harvard, Vancouver, ISO, and other styles

26

Hsu, Chou Jung, and Chia Wen Chang. "Unrelated Parallel-Machine Scheduling with Deteriorating Jobs and Rejection." Applied Mechanics and Materials 263-266 (December 2012): 655–59. http://dx.doi.org/10.4028/www.scientific.net/amm.263-266.655.

Full text

Abstract:

This paper aimed to investigate the unrelated parallel-machine scheduling with deteriorating jobs and rejection. The objective is to find the rejected jobs, the non-rejected jobs, and the optimal non-rejected job sequence so that the cost function that includes the weighted of total load, total completion time, and total absolute deviation of completion time plus the total penalty of the rejected jobs would be minimized. Results showed that the problem is polynomial time solvable when the number of machine is fixed.

APA, Harvard, Vancouver, ISO, and other styles

27

Kämpke, Thomas. "On the optimality of static priority policies in stochastic scheduling on parallel machines." Journal of Applied Probability 24, no. 2 (June 1987): 430–48. http://dx.doi.org/10.2307/3214267.

Full text

Abstract:

n jobs are to be preemptively scheduled for processing on n machines. The machines may have differing speeds and the jobs have processing requirements which are distributed as independent exponential random variables with different means. Holding cost g(U) is incurred per unit time that the set of uncompleted jobs is U and it is desired to minimize the total expected holding cost which is incurred until all jobs are complete. We show that if g satisfies certain simple conditions then the optimal policy is one which takes the jobs in the order 1, 2, ···, n and assigns each uncompleted job in turn to the fastest available machine. In the special case in which the objective is to minimize the expected weighted flowtime, where there is a holding cost of wi while job i is incomplete, the sufficient condition is simply w1 ≧ … ≧ wn and λ1 w1 ≧ … ≧ λn wn.

APA, Harvard, Vancouver, ISO, and other styles

28

Kämpke, Thomas. "On the optimality of static priority policies in stochastic scheduling on parallel machines." Journal of Applied Probability 24, no. 02 (June 1987): 430–48. http://dx.doi.org/10.1017/s0021900200031077.

Full text

Abstract:

n jobs are to be preemptively scheduled for processing on n machines. The machines may have differing speeds and the jobs have processing requirements which are distributed as independent exponential random variables with different means. Holding cost g(U) is incurred per unit time that the set of uncompleted jobs is U and it is desired to minimize the total expected holding cost which is incurred until all jobs are complete. We show that if g satisfies certain simple conditions then the optimal policy is one which takes the jobs in the order 1, 2, ···, n and assigns each uncompleted job in turn to the fastest available machine. In the special case in which the objective is to minimize the expected weighted flowtime, where there is a holding cost of wi while job i is incomplete, the sufficient condition is simply w1 ≧ … ≧ wn and λ1 w1 ≧ … ≧ λn wn .

APA, Harvard, Vancouver, ISO, and other styles

29

Oktafiani, Ayudita, and Muhammad Nashir Ardiansyah. "Scheduling Splitable Jobs on Identical Parallel Machines to Minimize Makespan using Mixed Integer Linear Programming." International Journal of Innovation in Enterprise System 7, no. 01 (January 31, 2023): 41–54. http://dx.doi.org/10.25124/ijies.v7i01.190.

Full text

Abstract:

The scheduling of parallel machines with and without a job-splitting property, deterministic demand, and sequence-independent setup time with the goal of minimizing makespan is examined in this work. For simultaneous processing by multiple machines, single-stage splitable jobs are broken into random (job) sections. When a job starts to be processed on a machine, an operator has to setup the machine for an hour. By creating two Mixed Integer Linear Programming models, this work proposes a mathematical programming strategy (MILP). A MILP model takes the job-splitting property into account. Another model, however, does not include the job-splitting property. This study investigates the performance of the proposed models using Gurobi solver. These programs' numerical calculations are based on actual problems in the Indonesian city of Bandung's plastics industry. On four identical parallel injection molding machines, 318 jobs must be finished in 22 periods. The real scheduling method is contrasted with these two MILP models. The maximum workload imbalance, the maximum relative percentage of imbalance, and the makespan of these three scheduling systems are used to evaluate their effectiveness. Without the job-splitting property, MILP can handle the real issue of scheduling identical parallel machines on injection molding machines to reduce makespan, resulting in a 36% average decrease. The MILP model's job-splitting property can reduce makespan by an additional 2.40%. The order of relative ranking is MILP with job-splitting property, MILP without job-splitting property, and actual scheduling based on the makespan minimization, workload imbalance, and relative percentage of imbalance.

APA, Harvard, Vancouver, ISO, and other styles

30

Chen, Jun, Bo Li, and Er Fei Wang. "Parallel Scheduling Algorithms Investigation of Support Strict Resource Reservation from Grid." Applied Mechanics and Materials 519-520 (February 2014): 108–13. http://dx.doi.org/10.4028/www.scientific.net/amm.519-520.108.

Full text

Abstract:

This paper studies resource reservation mechanisms in the strict parallel computing grid,and proposed to support the parallel strict resource reservation request scheduling model and algorithms, FCFS and EASY backfill analysis of two important parallel scheduling algorithm, given four parallel scheduling algorithms supporting resource reservation. Simulation results of four algorithms of resource utilization, job bounded slowdown factor and the success rate of Advanced Reservation (AR) jobs were studied. The results show that the EASY backfill + firstfit algorithm can ensure QoS of AR jobs while taking into account the performance of good non-AR jobs.

APA, Harvard, Vancouver, ISO, and other styles

31

Yang, Hong Bing, Fang Yan Mao, Jun Hao Xu, and Han Xiu Shi. "Parallel Machine Scheduling with Fuzzy due Date Using Improved Simulated Annealing in Lean Production." Applied Mechanics and Materials 457-458 (October 2013): 470–73. http://dx.doi.org/10.4028/www.scientific.net/amm.457-458.470.

Full text

Abstract:

Tardiness scheduling problems in the lean production has received extensive attention recently, and in most tardiness scheduling problems job due dates are regarded as invariable and known in advance. The study deals with fuzzy tardiness scheduling for parallel machines with fuzzy job due dates, where the objective is to minimize the average penalty cost of jobs tardiness. To describe the tardy degree of job clearly, a novel tardiness measure index is introduced based on the possibility and necessity measures in the study. And further, the mixed integer programming scheduling model of parallel machines is constructed for jobs tardiness. Since this problem is NP-hard, an improved simulated annealing is proposed and designed to solve the model. Finally, a numerical experiment is presented to illustrate the feasibility and effectiveness of the proposed method.

APA, Harvard, Vancouver, ISO, and other styles

32

Liu, Chun-Lai, and Jian-Jun Wang. "Unrelated Parallel-Machine Scheduling with Controllable Processing Times and Impact of Deteriorating Maintenance Activities under Consideration." Asia-Pacific Journal of Operational Research 33, no. 01 (February 2016): 1650001. http://dx.doi.org/10.1142/s0217595916500019.

Full text

Abstract:

In this paper, we study the problem of unrelated parallel machine scheduling with controllable processing times and deteriorating maintenance activity. The jobs are nonresumable. The processing time of each job is a linear function of the amount of a continuously divisible resource allocated to the job. During the planning horizon, there is at most one maintenance activity scheduled on each machine. Additionally, if the starting time of maintenance activity is delayed, the length of the maintenance activity required to perform will increase. Considering the total completion times of all jobs, the impact of maintenance activity in the form of the variation in machine load and the amounts of compression, we need to determine the job sequence on each machine, the location of maintenance activities and processing time compression of each job simultaneously. Accordingly, a polynomial time solution to the problem is provided.

APA, Harvard, Vancouver, ISO, and other styles

33

Cheng, Wenming, Peng Guo, Zeqiang Zhang, Ming Zeng, and Jian Liang. "Variable Neighborhood Search for Parallel Machines Scheduling Problem with Step Deteriorating Jobs." Mathematical Problems in Engineering 2012 (2012): 1–20. http://dx.doi.org/10.1155/2012/928312.

Full text

Abstract:

In many real scheduling environments, a job processed later needs longer time than the same job when it starts earlier. This phenomenon is known as scheduling with deteriorating jobs to many industrial applications. In this paper, we study a scheduling problem of minimizing the total completion time on identical parallel machines where the processing time of a job is a step function of its starting time and a deteriorating date that is individual to all jobs. Firstly, a mixed integer programming model is presented for the problem. And then, a modified weight-combination search algorithm and a variable neighborhood search are employed to yield optimal or near-optimal schedule. To evaluate the performance of the proposed algorithms, computational experiments are performed on randomly generated test instances. Finally, computational results show that the proposed approaches obtain near-optimal solutions in a reasonable computational time even for large-sized problems.

APA, Harvard, Vancouver, ISO, and other styles

34

Bambos, Nicholas, and Jean Walrand. "Scheduling and stability aspects of a general class of parallel processing systems." Advances in Applied Probability 25, no. 1 (March 1993): 176–202. http://dx.doi.org/10.2307/1427501.

Full text

Abstract:

In this paper we study the following general class of concurrent processing systems. There are several different classes of processors (servers) and many identical processors within each class. There is also a continuous random flow of jobs, arriving for processing at the system. Each job needs to engage concurrently several processors from various classes in order to be processed. After acquiring the needed processors the job begins to be executed. Processing is done non-preemptively, lasts for a random amount of time, and then all the processors are released simultaneously. Each job is specified by its arrival time, its processing time, and the list of processors that it needs to access simultaneously. The random flow (sequence) of jobs has a stationary and ergodic structure. There are several possible policies for scheduling the jobs on the processors for execution; it is up to the system designer to choose the scheduling policy to achieve certain objectives.We focus on the effect that the choice of scheduling policy has on the asymptotic behavior of the system at large times and especially on its stability, under general stationary and ergocic input flows.

APA, Harvard, Vancouver, ISO, and other styles

35

LIU, MING, YINFENG XU, CHENGBIN CHU, and FEIFENG ZHENG. "ONLINE SCHEDULING OF PARALLEL JOBS WITH BOUNDED PROCESSING TIMES ON TWO MACHINES." Discrete Mathematics, Algorithms and Applications 02, no. 03 (September 2010): 425–32. http://dx.doi.org/10.1142/s1793830910000760.

Full text

Abstract:

We study the problem of online scheduling parallel jobs with bounded processing times on 2 machines, and the objective is to minimize makespan. A parallel job requires simultaneous processing on a pre-specified, job-dependent number of machines. The problem is online in the sense that jobs are presented one by one. Once a job is presented, we must irrevocably assign it to some time slot before the next one shows up. We investigate the case where the processing times of jobs are bounded within interval [a, αa] where a > 0 and α > 1. We first prove a lower bound of competitive ratios for online algorithms equal [Formula: see text] when α ≥ 2 and [Formula: see text] when 1 < α < 2, respectively. We further prove that the Greedy algorithm proposed in Chan et al. (2008) is [Formula: see text]-competitive in the case but it cannot be better than [Formula: see text]-competitive. The results imply that when 1 < α < 2 Greedy has a competitive ratio better than 2, which is the competitive ratio of Greedy in the case without processing time bound.

APA, Harvard, Vancouver, ISO, and other styles

36

Bambos, Nicholas, and Jean Walrand. "Scheduling and stability aspects of a general class of parallel processing systems." Advances in Applied Probability 25, no. 01 (March 1993): 176–202. http://dx.doi.org/10.1017/s0001867800025222.

Full text

Abstract:

In this paper we study the following general class of concurrent processing systems. There are several different classes of processors (servers) and many identical processors within each class. There is also a continuous random flow of jobs, arriving for processing at the system. Each job needs to engage concurrently several processors from various classes in order to be processed. After acquiring the needed processors the job begins to be executed. Processing is done non-preemptively, lasts for a random amount of time, and then all the processors are released simultaneously. Each job is specified by its arrival time, its processing time, and the list of processors that it needs to access simultaneously. The random flow (sequence) of jobs has a stationary and ergodic structure. There are several possible policies for scheduling the jobs on the processors for execution; it is up to the system designer to choose the scheduling policy to achieve certain objectives. We focus on the effect that the choice of scheduling policy has on the asymptotic behavior of the system at large times and especially on its stability, under general stationary and ergocic input flows.

APA, Harvard, Vancouver, ISO, and other styles

37

Li, Wenhua, Libo Wang, Xing Chai, and Hang Yuan. "Online Batch Scheduling of Simple Linear Deteriorating Jobs with Incompatible Families." Mathematics 8, no. 2 (February 1, 2020): 170. http://dx.doi.org/10.3390/math8020170.

Full text

Abstract:

We considered the online scheduling problem of simple linear deteriorating job families on m parallel batch machines to minimize the makespan, where the batch capacity is unbounded. In this paper, simple linear deteriorating jobs mean that the actual processing time p j of job J j is assumed to be a linear function of its starting time s j , i.e., p j = α j s j , where α j > 0 is the deterioration rate. Job families mean that one job must belong to some job family, and jobs of different families cannot be processed in the same batch. When m = 1 , we provide the best possible online algorithm with the competitive ratio of ( 1 + α max ) f , where f is the number of job families and α max is the maximum deterioration rate of all jobs. When m ≥ 1 and m = f , we provide the best possible online algorithm with the competitive ratio of 1 + α max .

APA, Harvard, Vancouver, ISO, and other styles

38

Yu, Ganhua. "A Coordination Mechanism for Scheduling Game on Parallel-Batch Machines with Deterioration Jobs." Mathematical Problems in Engineering 2022 (December 17, 2022): 1–7. http://dx.doi.org/10.1155/2022/3780331.

Full text

Abstract:

In this study, we consider a parallel-batch machines scheduling game problem with deterioration jobs. The processing time of a job is a simple linear function of its starting time. Each of the parallel-batch machines can process up to B jobs simultaneously as a batch. The processing time of a batch is the processing time of the job with the longest deteriorating rate in the batch. All jobs in the same batch start and complete at the same time. Each job as an agent and its individual cost is the completion time of the job. We present a coordination mechanism for the scheduling game problem with social cost of minimizing the makespan in this paper, namely fully batch longest deteriorating rate. For this problem, we precisely quantify the inefficiency of Nash equilibrium by the logarithm price of anarchy. It is defined to be the ratio between the logarithm of social cost of the worst Nash equilibrium and the logarithm of social cost of an optimum schedule. In addition, we discuss the existence of Nash equilibrium and present an upper bound and lower bounds on the logarithm price of anarchy of the coordination mechanism. We show that the mechanism has a logarithm price of anarchy at most 2 − 1 / 3 m a x m , B − 2 / 3 B .

APA, Harvard, Vancouver, ISO, and other styles

39

Zhang, Guang-Qian, Jian-Jun Wang, and Ya-Jing Liu. "Scheduling Jobs with Variable Job Processing Times on Unrelated Parallel Machines." Scientific World Journal 2014 (2014): 1–7. http://dx.doi.org/10.1155/2014/242107.

Full text

Abstract:

munrelated parallel machines scheduling problems with variable job processing times are considered, where the processing time of a job is a function of its position in a sequence, its starting time, and its resource allocation. The objective is to determine the optimal resource allocation and the optimal schedule to minimize a total cost function that dependents on the total completion (waiting) time, the total machine load, the total absolute differences in completion (waiting) times on all machines, and total resource cost. If the number of machines is a given constant number, we propose a polynomial time algorithm to solve the problem.

APA, Harvard, Vancouver, ISO, and other styles

40

Zhang, Qi, and Cheng Xin Luo. "Uniform Parallel-Machine Scheduling with Deteriorating Jobs and Rejection." Applied Mechanics and Materials 644-650 (September 2014): 2030–33. http://dx.doi.org/10.4028/www.scientific.net/amm.644-650.2030.

Full text

Abstract:

This paper considers uniform parallel-machine scheduling with linear deterioration and rejection. The processing time of a job is a linear increasing function of its starting time and jobs can be rejected by paying penalties. The objective is to find a schedule which minimizes the time by which all jobs are delivered. We propose a fully polynomial-time approximation scheme to solve this problem.

APA, Harvard, Vancouver, ISO, and other styles

41

Yin, Yunqiang, Shuenn-Ren Cheng, and Chin-Chia Wu. "Parallel-Machine Scheduling to Minimize Flowtime, Holding, and Batch Delivery Costs." Asia-Pacific Journal of Operational Research 31, no. 06 (December 2014): 1450044. http://dx.doi.org/10.1142/s0217595914500444.

Full text

Abstract:

This paper considers a batch delivery scheduling problem in which n independent and simultaneously available jobs are to be processed on m unrelated or uniform parallel machines. The jobs scheduled on the same machine are delivered in batches to customers and the delivery date of a batch equals the completion time of the last job in the batch. The number of jobs in each delivery batch is constrained by the batch size, and the cost of delivering a batch depends not only on the number of jobs in the batch but also on the machine on which the batch is processed. The objective is to find jointly the optimal number of batches on each machine, the optimal assignment of jobs to the batches, and the optimal job processing sequence to minimize the sum of total flowtime, total holding time, and delivery costs. When the number of batches has a fixed upper bound, we present polynomial-time algorithms to solve the problems with unrelated and uniform parallel machines. If the bound constraint on the number of batches is relaxed, we provide polynomial-time algorithms to solve two special cases of the problem with uniform parallel machines.

APA, Harvard, Vancouver, ISO, and other styles

42

Brevik, John, Daniel Nurmi, and Rich Wolski. "Using Model-based Clustering to Improve Predictions for Queueing Delay on Parallel Machines." Parallel Processing Letters 17, no. 01 (March 2007): 21–46. http://dx.doi.org/10.1142/s0129626407002855.

Full text

Abstract:

Most space-sharing parallel computers presently operated by production high-performance computing centers use batch-queuing systems to manage processor allocation. In many cases, users wishing to use these batch-queued resources may choose among different queues (charging different amounts) potentially on a number of machines to which they have access. In such a situation, the amount of time a user's job will wait in any one batch queue can be a significant portion of the overall time from job submission to job completion. It thus becomes desirable to provide a prediction for the amount of time a given job can expect to wait in the queue. Further, it is natural to expect that attributes of an incoming job, specifically the number of processors requested and the amount of time requested, might impact that job's wait time. In this work, we explore the possibility of generating accurate predictions by automatically grouping jobs having similar attributes using model-based clustering. Moreover, we implement this clustering technique for a time series of jobs so that predictions of future wait times can be generated in real time. Using trace-based simulation on data from 7 machines over a 9-year period from across the country, comprising over one million job records, we show that clustering either by requested time, requested number of processors, or the product of the two generally produces more accurate predictions than earlier, more naive, approaches and that automatic clustering outperforms administrator-determined clustering.

APA, Harvard, Vancouver, ISO, and other styles

43

Chang, Cheng-Shang, Arie Hordijk, Rhonda Righter, and Gideon Weiss. "The Stochastic Optimality of SEPT in Parallel Machine Scheduling." Probability in the Engineering and Informational Sciences 8, no. 2 (April 1994): 179–88. http://dx.doi.org/10.1017/s0269964800003326.

Full text

Abstract:

We consider preemptive scheduling on parallel machines where processing times of jobs are i.i.d. but jobs may already have received distinct amounts of service. We show that when processing times are increasing in likelihood ratio, SEPT (shortest expected [remaining] processing time first) stochastically minimizes any increasing and Schur-concave function of the job completion times. The same result holds when processing times are exponential with possibly different means.

APA, Harvard, Vancouver, ISO, and other styles

44

Lin, Hong. "A Case Study of Teaching Parallel and Distributed Computing Topics on a Computer Cluster." Journal of Cases on Information Technology 16, no. 2 (April 2014): 58–71. http://dx.doi.org/10.4018/jcit.2014040105.

Full text

Abstract:

This paper presents the establishment of cluster computing lab at a minority serving institution that aims to provide computing resources to support undergraduate computer science curriculum. The computing resources of the cluster are managed by a job distribution environment that allows the users to upload, compile, and run their jobs. The job distribution software distributes the submitted jobs to the computing nodes of the cluster. The authors will present a case study of using this platform to teach parallel and distributed computing topics in the operating system course. The evaluation of the teaching effectiveness is presented thereafter.

APA, Harvard, Vancouver, ISO, and other styles

45

Righter, Rhonda, and Susan H. Xu. "Scheduling jobs on non-identical IFR processors to minimize general cost functions." Advances in Applied Probability 23, no. 4 (December 1991): 909–24. http://dx.doi.org/10.2307/1427683.

Full text

Abstract:

We consider the problem of scheduling n jobs non-preemptively on m parallel, non-identical processors to minimize a weighted expected cost function of job completion times, where the weights are associated with the jobs. The cost function is assumed to be increasing and concave but otherwise arbitrary. Processing times are IFR with different distributions for different processors. Jobs may be processed on any processor and there are no precedences. We show that the optimal policy orders the jobs in decreasing order of their weights and then uses the individually optimal policy for each job. In other words, processors are offered to jobs in order, and each job considers its own expected cost function for its completion time to decide whether to accept or reject a processor. Therefore, the optimal policy does not depend on the weights of the jobs except through their order. Special cases of our objective function are weighted expected flowtime, weighted discounted expected flowtime, and weighted expected number of tardy jobs.

APA, Harvard, Vancouver, ISO, and other styles

46

Righter, Rhonda, and Susan H. Xu. "Scheduling jobs on non-identical IFR processors to minimize general cost functions." Advances in Applied Probability 23, no. 04 (December 1991): 909–24. http://dx.doi.org/10.1017/s0001867800024010.

Full text

Abstract:

We consider the problem of scheduling n jobs non-preemptively on m parallel, non-identical processors to minimize a weighted expected cost function of job completion times, where the weights are associated with the jobs. The cost function is assumed to be increasing and concave but otherwise arbitrary. Processing times are IFR with different distributions for different processors. Jobs may be processed on any processor and there are no precedences. We show that the optimal policy orders the jobs in decreasing order of their weights and then uses the individually optimal policy for each job. In other words, processors are offered to jobs in order, and each job considers its own expected cost function for its completion time to decide whether to accept or reject a processor. Therefore, the optimal policy does not depend on the weights of the jobs except through their order. Special cases of our objective function are weighted expected flowtime, weighted discounted expected flowtime, and weighted expected number of tardy jobs.

APA, Harvard, Vancouver, ISO, and other styles

47

Janiak, A., W. Janiak, and M. Y. Kovalyov. "Due window assignment and scheduling on parallel machines: a FPTAS for a bottleneck criterion." Bulletin of the Polish Academy of Sciences Technical Sciences 62, no. 4 (December 1, 2014): 805–8. http://dx.doi.org/10.2478/bpasts-2014-0088.

Full text

Abstract:

Abstract A fully polynomial time approximation scheme (FPTAS) with run time is developed for a problem which combines common due window assignment and scheduling n jobs on m identical parallel machines. The problem criterion is bottleneck (min-max) such that the maximum cost, which includes job earliness, job tardiness and due window size costs, is minimized.

APA, Harvard, Vancouver, ISO, and other styles

48

LIU, MING, and CHENGBIN CHU. "OPTIMAL SEMI-ONLINE ALGORITHMS FOR m-BATCH-MACHINE FLOW SHOP SCHEDULING." Discrete Mathematics, Algorithms and Applications 04, no. 04 (December 2012): 1250051. http://dx.doi.org/10.1142/s1793830912500516.

Full text

Abstract:

This paper deals with semi-online scheduling on m-batch-machine flow shop. The objective is to minimize the makespan. A parallel batch processing machine can handle up to B jobs simultaneously. We study an unbounded model where B = ∞. The jobs that are processed together construct a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. The problem is online in the sense that jobs arrive over time. Let pi, j(i = 1,…,m) denote the processing time of job Jj on machines Mi, respectively. Let Jj+1 be the following job of Jj in a job instance. We study semi-online problem with jobs' nondecreasing processing times. We focus on the case where p1, j = ⋯ = pm, j for i = 1, …, m and pi, j+1 ≥ βpi, j (β ≥ 1). For this problem, we propose an optimal algorithm [Formula: see text] with a competitive ratio [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

49

Schiefermayr, Klaus, and Josef Weichbold. "A complete solution for the optimal stochastic scheduling of a two-stage tandem queue with two flexible servers." Journal of Applied Probability 42, no. 3 (September 2005): 778–96. http://dx.doi.org/10.1239/jap/1127322027.

Full text

Abstract:

We consider a two-stage tandem queue with two parallel servers and two queues. We assume that initially all jobs are present and that no further arrivals take place at any time. The two servers are identical and can serve both types of job. The processing times are exponentially distributed. After being served, a job of queue 1 joins queue 2, whereas a job of queue 2 leaves the system. Holding costs per job and per unit time are incurred if there are jobs holding in the system. Our goal is to find the optimal strategy that minimizes the expected total holding costs until the system is cleared. We give a complete solution for the optimal control of all possible parameters (costs and service times), especially for those parameter regions in which the optimal control depends on how many jobs are present in the two queues.

APA, Harvard, Vancouver, ISO, and other styles

50

Schiefermayr, Klaus, and Josef Weichbold. "A complete solution for the optimal stochastic scheduling of a two-stage tandem queue with two flexible servers." Journal of Applied Probability 42, no. 03 (September 2005): 778–96. http://dx.doi.org/10.1017/s0021900200000772.

Full text

Abstract:

We consider a two-stage tandem queue with two parallel servers and two queues. We assume that initially all jobs are present and that no further arrivals take place at any time. The two servers are identical and can serve both types of job. The processing times are exponentially distributed. After being served, a job of queue 1 joins queue 2, whereas a job of queue 2 leaves the system. Holding costs per job and per unit time are incurred if there are jobs holding in the system. Our goal is to find the optimal strategy that minimizes the expected total holding costs until the system is cleared. We give a complete solution for the optimal control of all possible parameters (costs and service times), especially for those parameter regions in which the optimal control depends on how many jobs are present in the two queues.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Job parallèle'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles