Journal articles: 'Parallel job'

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

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

3

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

4

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

5

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

6

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

7

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

8

Schwiegelshohn, Uwe, and Ramin Yahyapour. "Fairness in parallel job scheduling." Journal of Scheduling 3, no. 5 (2000): 297–320. http://dx.doi.org/10.1002/1099-1425(200009/10)3:5<297::aid-jos50>3.0.co;2-d.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

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

10

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

11

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

12

Singh, Priya, Zafruddin Quadri, and Anuj Kumar. "Comparative Study of Parallel Scheduling Algorithm for Parallel Job." International Journal of Computer Applications 134, no. 10 (January 15, 2016): 10–14. http://dx.doi.org/10.5120/ijca2016908061.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

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

14

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

15

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

16

Berg, Benjamin, Jan-Pieter Dorsman, and Mor Harchol-Balter. "Towards Optimality in Parallel Job Scheduling." ACM SIGMETRICS Performance Evaluation Review 46, no. 1 (January 17, 2019): 116–18. http://dx.doi.org/10.1145/3308809.3308870.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Berg, Benjamin, Jan-Pieter Dorsman, and Mor Harchol-Balter. "Towards Optimality in Parallel Job Scheduling." ACM SIGMETRICS Performance Evaluation Review 46, no. 1 (January 17, 2019): 116–18. http://dx.doi.org/10.1145/3292040.3219666.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

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

19

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

20

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

21

DA SILVA, FABRICIO ALVES BARBOSA, and ISAAC D. SCHERSON. "EFFICIENT PARALLEL JOB SCHEDULING USING GANG SERVICE." International Journal of Foundations of Computer Science 12, no. 03 (June 2001): 265–84. http://dx.doi.org/10.1142/s0129054101000485.

Full text

Abstract:

Gang scheduling has been widely used as a practical solution to the dynamic parallel job scheduling problem. To overcome some of the limitations of traditional Gang scheduling algorithms, Concurrent Gang is proposed as a class of scheduling policies which allows the flexible and simultaneous scheduling of multiple parallel jobs. It hence improves the space sharing characteristics of Gang scheduling while preserving all other advantages. To provide a sound analysis of Concurrent Gang performance, a novel methodology based on the traditional concept of competitive ratio is also introduced. Dubbed dynamic competitive ratio, the new method is used to compare dynamic bin packing algorithms used in this paper. These packing algorithms apply to the Concurrent Gang scheduling of a workload generated by a statistical model. Moreover, dynamic competitive ratio is the figure of merit used to evaluate and compare packing strategies for job scheduling under multiple constraints. It will be shown that for the unidimensional case there is a small difference between the performance of best fit and first fit; first fit can hence be used without significant system degradation. For the multidimensional case, when memory is also considered, we concluded that the packing algorithm must try to balance the resource utilization in all dimensions simulataneously, instead of given priority to only one dimension of the problem.

APA, Harvard, Vancouver, ISO, and other styles

22

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

23

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

24

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

25

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

26

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

27

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

28

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

29

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

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, 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

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

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

35

Kusuma, Felia Indah, and ParwadiMoengin. "A Mathematical Model for Simultaneous Parallel Multiple Source Scheduling Problems." International Journal of Advanced Engineering and Management Research 08, no. 01 (2023): 38–48. http://dx.doi.org/10.51505/ijaemr.2023.8104.

Full text

Abstract:

Manufacturing companies engaged in textile manufacturing engaged in the Job Order system with an extensive net work and market orientation require companies to pay attention to product quality and services that meet consumer requirements, one of which is by fulfilling orders at a pre-agreed time. The problem that is often found in companies like this is the frequent delays in completing orders. This is caused by the less optimal scheduling of job orders with different weights or penalties for each job which will ultimately result in a large total weighted delay originating from the accumulation of job delays with these different weights. This paper is intended to help companies create a new, more optimal schedule with the aim of minimizing the total weighted delay of order completion. The model proposed in this paper is a mathematical model for simultaneous parallel multiplesource scheduling problems for multiple-jobs and multiple-operations. The initial step of using this model is the formulation of decision variables, the objective function is minimizing tardiness or total weighted delay, and limiting functions. After the jobs to be examined are formulated into a model, data processing is carried out using a computerized system. The software used in processing this data is Win QSB. At the end of the paper a numerical example is given to use the proposed model. From data processing using Win QSB, it can be seen how much total weighted delay is obtained from scheduling with an integer linear programming model for this scheduling.

APA, Harvard, Vancouver, ISO, and other styles

36

Wright, Paul E. "Two parallel processors with coupled inputs." Advances in Applied Probability 24, no. 4 (December 1992): 986–1007. http://dx.doi.org/10.2307/1427722.

Full text

Abstract:

We consider the double queue arising from a system consisting of two processors serving three job streams generated by independent Poisson sources. The central job stream of rate v consists of jobs which place resource demands on both processors, which are handled separately by each processor once the request is made. In addition, the first processor receives background work at a rate of λwhile the second receives similar tasks at a rate η. Each processor has exponentially distributed service times with rates α and β respectively. A functional equation is found for P(z, w), the generating function of the joint queue-length distribution, which leads to a relation between P(z, 0) and P(0, w) in the region |z|, |w| < 1 of a complex algebraic curve associated with the problem. The curve is parametrized by elliptic functions z(ξ) and w(ξ) and the relation between Ρ (z(ξ), 0) and P(0, w(ξ)) persists on their analytic continuation as elliptic functions in the ξ-plane. This leads to their eventual determination by an appeal to the theory of elliptic functions. From this determination we obtain asymptotic limit laws for the expectations of the mean number of jobs in each queue conditioned on the other, as the number of jobs in both processors tends to∞. Transitions are observed in the asymptotic behavior of these quantities as one crosses various boundaries in the parameter space. An interpretation of these results via the theory of large deviations is presented.

APA, Harvard, Vancouver, ISO, and other styles

37

Wright, Paul E. "Two parallel processors with coupled inputs." Advances in Applied Probability 24, no. 04 (December 1992): 986–1007. http://dx.doi.org/10.1017/s0001867800025040.

Full text

Abstract:

We consider the double queue arising from a system consisting of two processors serving three job streams generated by independent Poisson sources. The central job stream of rate v consists of jobs which place resource demands on both processors, which are handled separately by each processor once the request is made. In addition, the first processor receives background work at a rate of λwhile the second receives similar tasks at a rate η. Each processor has exponentially distributed service times with rates α and β respectively. A functional equation is found for P(z, w), the generating function of the joint queue-length distribution, which leads to a relation between P(z, 0) and P(0, w) in the region |z|, |w| < 1 of a complex algebraic curve associated with the problem. The curve is parametrized by elliptic functions z(ξ) and w(ξ) and the relation between Ρ (z(ξ), 0) and P(0, w(ξ)) persists on their analytic continuation as elliptic functions in the ξ-plane. This leads to their eventual determination by an appeal to the theory of elliptic functions. From this determination we obtain asymptotic limit laws for the expectations of the mean number of jobs in each queue conditioned on the other, as the number of jobs in both processors tends to∞. Transitions are observed in the asymptotic behavior of these quantities as one crosses various boundaries in the parameter space. An interpretation of these results via the theory of large deviations is presented.

APA, Harvard, Vancouver, ISO, and other styles

38

Lee, Jun-Ho, and Hoon Jang. "Uniform Parallel Machine Scheduling with Dedicated Machines, Job Splitting and Setup Resources." Sustainability 11, no. 24 (December 13, 2019): 7137. http://dx.doi.org/10.3390/su11247137.

Full text

Abstract:

We examine a uniform parallel machine scheduling problem with dedicated machines, job splitting, and limited setup resources for makespan minimization. In this problem, machines have different processing speeds, and each job can only be processed at several designated machines. A job can be split into multiple sections and those sections can be processed on multiple machines simultaneously. Sequence-independent setup times are assumed, and setup operations between jobs require setup operators that are limited. For the problem, we first develop a mathematical optimization model and for large-sized problems a constructive heuristic algorithm is proposed. Finally, we show that the algorithm developed is efficient and provides good solutions by experiments with various scenarios.

APA, Harvard, Vancouver, ISO, and other styles

39

Rudy, Jarosław. "Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time." Applied Sciences 11, no. 17 (September 3, 2021): 8204. http://dx.doi.org/10.3390/app11178204.

Full text

Abstract:

In this paper, a flow shop scheduling problem with minimal and maximal machine idle time with the goal of minimizing makespan is considered. The mathematical model of the problem is presented. A generalization of the prefix sum, called the job shift scan, for computing required shifts for overlapping jobs is proposed. A work-efficient algorithm for computing the job shift scan in parallel for the PRAM model with n processors is proposed and its time complexity of O(logn) is proven. Then, an algorithm for computing the makespan in time O(mlogn) in parallel using the prefix sum and job shift scan is proposed. Computer experiments on GPU were conducted using the CUDA platform. The results indicate multi-thread GPU vs. single-thread GPU speedups of up to 350 and 1000 for job shift scan and makespan calculation algorithms, respectively. Multi-thread GPU vs. single-thread CPU speedups up to 4.5 and 14.7, respectively, were observed as well. The experiments on the Taillard-based problem instances using a simulated annealing solving method and employing the parallel makespan calculation show that the method is able to perform many more iterations in the given time limit and obtain better results than the non-parallel version.

APA, Harvard, Vancouver, ISO, and other styles

40

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

41

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

42

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

43

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

44

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

45

Bambos, Nicholas, and George Michailidis. "ON PARALLEL QUEUING WITH RANDOM SERVER CONNECTIVITY AND ROUTING CONSTRAINTS." Probability in the Engineering and Informational Sciences 16, no. 2 (April 2002): 185–203. http://dx.doi.org/10.1017/s0269964802162048.

Full text

Abstract:

We study systems of parallel queues with finite buffers, a single server with random connectivity to each queue, and arriving job flows with random or class-dependent accessibility to the queues. Only currently connected queues may receive (preemptive) service at any given time, whereas an arriving job can only join one of its accessible queues. Using the coupling method, we study three key models, progressively building from simpler to more complicated structures.In the first model, there are only random server connectivities. It is shown that allocating the server to the Connected queue with the Fewest Empty Spaces (C-FES) stochastically minimizes the number of lost jobs due to buffer overflows, under conditions of independence and symmetry.In the second model, we additionally consider random accessibility of queues by arriving jobs. It is shown that allocating the server to the C-FES and routing each arriving job to the currently Accessible queue with the Most Empty Spaces (C-FES/A-MES) minimizes the loss flow stochastically, under similar assumptions.In the third model (addressing a target application), we consider multiple classes of arriving job flows, each allowed access to a deterministic subset of the queues. Under analogous assumptions, it is again shown that the C-FES/A-MES policy minimizes the loss flow stochastically.The random connectivity/accessibility aspect enhances significantly the structure and application scope of the classical parallel queuing model. On the other hand, it introduces essential additional dynamics and considerable complications. It is interesting that a simple policy like FES/MES, known to be optimal for the classical model, extends to the C-FES/A-MES in our case.

APA, Harvard, Vancouver, ISO, and other styles

46

Dong, Jianming, Xueshi Wang, Liliang Wang, and Jueliang Hu. "Parallel machine scheduling with job delivery coordination." ANZIAM Journal 58 (July 20, 2017): 306. http://dx.doi.org/10.21914/anziamj.v58i0.11054.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Karatza, Helen D., and Ralph C. Hilzer. "Parallel Job Scheduling in Homogeneous Distributed Systems." SIMULATION: Transactions of the Society for Modeling and Simulation 79, no. 5 (May 1, 2003): 287–98. http://dx.doi.org/10.1177/003754903037148.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Dileepan, Parthasarati, and Tapan Sen. "Job Tardiness in Unequal Parallel Processor Systems." Journal of Information and Optimization Sciences 10, no. 3 (September 1989): 579–90. http://dx.doi.org/10.1080/02522667.1989.10698988.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Karatza, Helen D., and Ralph C. Hilzer. "Parallel Job Scheduling in Homogeneous Distributed Systems." SIMULATION 79, no. 5-6 (May 2003): 287–98. http://dx.doi.org/10.1177/0037549703037148.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

JOO, UN GI. "JOB ASSIGNMENT ALGORITHMS ON UNIFORM PARALLEL MACHINES." Engineering Optimization 33, no. 3 (February 2001): 351–71. http://dx.doi.org/10.1080/03052150108940924.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Parallel job'

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