检索结果-内蒙古大学图书馆

Minimizing worst-case and average-case makespan over scenarios

JOURNAL OF scheduling 2017年第6期20卷 545-555页

作者： Feuerstein, Esteban Marchetti-Spaccamela, Alberto Schalekamp, Frans Sitters, Rene van der Ster, Suzanne Stougie, Leen van Zuylen, Anke Univ Buenos Aires Buenos Aires DF Argentina Sapienza Univ Roma Rome Italy Cornell Univ Ithaca NY USA Vrije Univ Amsterdam Amsterdam Netherlands CWI Amsterdam Netherlands Tech Univ Munich Munich Germany Coll William & Mary Williamsburg VA USA

We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all scenarios in an explicitly given set. Each scenario is a subset of jobs that must be executed in that scenario. the two objectives that we consider are minimizing the maximum makespan over all scenarios and minimizing the sum of the makespans of all scenarios. For both versions, we give several approximation algorithms and lower bounds on their approximability. We also consider some (easier) special cases. Combinatorial optimization problems under scenarios in general, and scheduling problems under scenarios in particular, have seen only limited research attention so far. With this paper, we make a step in this interesting research direction.

关键词： Job scheduling Approximation algorithm Makespan Scenarios

来源：评论

学校读者我要写书评

暂无评论

scheduling multipacket frames with frame deadlines

引用

JOURNAL OF scheduling 2017年第6期20卷 623-634页

作者： Jez, Lukasz Mansour, Yishay Patt-Shamir, Boaz Univ Wroclaw Inst Comp Sci Ul Joliot Curie 15 PL-50383 Wroclaw Poland Tel Aviv Univ Blavatnik Sch Comp Sci Tel Aviv Israel Microsoft Res Herzliyya Israel Tel Aviv Univ Sch Elect Engn Tel Aviv Israel

We consider scheduling information units called frames, each with a delivery deadline. Frames consist of packets, which arrive online in a roughly periodic fashion, and compete on allocation of transmission slots. A frame is deemed useful only if all its packets are delivered before its deadline. We focus on a "proportional" variant, where the value of each frame is proportional to its size, but the sizes and periods of the frames are arbitrary. We give a constant-competitive algorithm for this setting, assuming bounded jitter and some slack in the frames' deadlines, the latter of which is necessary. Using standard techniques, our algorithm yields polylog-competitive algorithms for general instances with slack and bounded jitter.

关键词： scheduling Online algorithms Communication networks

来源：评论

学校读者我要写书评

暂无评论

Single machine scheduling with a generalized job-dependent cumulative effect

引用

JOURNAL OF scheduling 2017年第6期20卷 583-592页

作者： Rustogi, Kabir Strusevich, Vitaly A. Univ Greenwich Dept Math Sci Old Royal Naval Coll London SE10 9LS England

We consider a single machine scheduling problem with changing processing times. the processing conditions are subject to a general cumulative effect, in which the processing time of a job depends on the sum of certain parameters associated with previously scheduled jobs. In previous papers, these parameters are assumed to be equal to the normal processing times of jobs, which seriously limits the practical application of this model. We further generalize this model by allowing every job to respond differently to these cumulative effects. For the introduced model, we solve the problem of minimizing the makespan, with and without precedence constraints. For the problem without precedence constraints, we also consider a situation in which a maintenance activity is included in the schedule, which can improve the processing conditions of the machine, not necessarily to its original state. the resulting problem is reformulated as a variant of a Boolean programming problem with a quadratic objective, known as a half-product, which allows us to develop a fully polynomial-time approximation scheme with the best possible running time.

关键词： Single machine Deterioration Precedence constraints Maintenance Approximation scheme Half product problem

来源：评论

学校读者我要写书评

暂无评论

LP rounding and combinatorial algorithms for minimizing active and busy time

引用

JOURNAL OF scheduling 2017年第6期20卷 657-680页

作者： Chang, Jessica Khuller, Samir Mukherjee, Koyel Univ Maryland College Pk MD 20742 USA

We consider fundamental scheduling problems motivated by energy issues. In this framework, we are given a set of jobs, each with a release time, deadline, and required processing length. the jobs need to be scheduled on a machine so that at most g jobs are active at any given time. the duration for which a machine is active (i.e., "on") is referred to as its active time. the goal is to find a feasible schedule for all jobs, minimizing the total active time. When preemption is allowed at integer time points, we show that a minimal feasible schedule already yields a 3-approximation (and this bound is tight) and we further improve this to a 2-approximation via LP rounding techniques. Our second contribution is for the non-preemptive version of this problem. However, since even asking if a feasible schedule on one machine exists is NP-hard, we allow for an unbounded number of virtual machines, each having capacity of g. this problem is known as the busy time problem in the literature and a 4-approximation is known for this problem. We develop a new combinatorial algorithm that gives a 3-approximation. Furthermore, we consider the preemptive busy time problem, giving a simple and exact greedy algorithm when unbounded parallelism is allowed, i.e., g is unbounded. For arbitrary g, this yields an algorithm that is 2-approximate.

关键词： Active time Busy time Batch scheduling

来源：评论

学校读者我要写书评

暂无评论

Complexity results for an integrated single machine scheduling and outbound delivery problem with fixed sequence

引用

JOURNAL OF scheduling 2017年第6期20卷 681-693页

作者： Cheref, Azeddine Agnetis, Alessandro Artigues, Christian Billaut, Jean-Charles Univ Tours CNRS LI EA 6300 ERL CNRS 6305 64 Ave Jean Portalis F-37200 Tours France Univ Toulouse CNRS LAAS CNRS Toulouse France Univ Siena Dipartimento Ingn Informaz Via Roma 56 I-53100 Siena Italy

In this paper, we consider an integrated production and outbound delivery scheduling problem. In particular, we address the situation in which the scheduling sequence and the delivery sequence are the same and predefined. A set of jobs are processed on a single machine, and finished jobs are delivered to the customers by a single capacitated vehicle. Each job has a processing time, and transportation times between customers are taken into account. Because the sequence is given, the problem consists in forming batches of jobs and our objective is to minimize the sum of the delivery times or general functions of the delivery times. the NP-hardness of the general problem is established, and a pseudopolynomial time dynamic programming algorithm is given. Some particular cases are treated, for which NP-hardness proofs and polynomial time algorithms are given. Finally, a fixed-parameter tractability result is given.

关键词： scheduling Delivery Batching Complexity Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Approximation for scheduling on uniform nonsimultaneous parallel machines

引用

JOURNAL OF scheduling 2017年第6期20卷 593-600页

作者： Grigoriu, Liliana Friesen, Donald K. Univ Siegen Fak Wirtschaftswissensch Wirtschaftsinformat & Wi Kohlbettstr 15 D-57068 Siegen Germany Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

We consider the problem of scheduling on uniform machines which may not start processing at the same time with the purpose of minimizing the maximum completion time. We propose using a variant of the MULTIFIT algorithm, LMULTIFIT, which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and within times the optimal maximum completion time for problem instances with two machines. Both developments represent improvements over previous results. We prove that LMULTIFIT worst-case bounds for scheduling on simultaneous uniform machines are also LMULTIFIT worst-case approximation bounds for scheduling on nonsimultaneous uniform machines and show that worst-case approximation bounds of MULTIFIT variants for simultaneous uniform machines from previous literature also apply to LMULTIFIT. We also comment on how a PTAS for scheduling on a constant number of uniform machines with fixed jobs can be used to obtain a PTAS for scheduling on a constant number of uniform nonsimultaneous parallel machines.

关键词： Multiprocessor scheduling Uniform processors MULTIFIT Nonsimultaneous start times Worst-case bounds Makespan

来源：评论

学校读者我要写书评

暂无评论

Fault tolerant scheduling of tasks of two sizes under resource augmentation

引用

JOURNAL OF scheduling 2017年第6期20卷 695-711页

作者： Kowalski, Dariusz R. Wong, Prudence W. H. Zavou, Elli Univ Liverpool Ashton BldgAshton St Liverpool L69 3BX Merseyside England Univ Carlos III Madrid Avda Mar Mediterraneo 22 Madrid 28918 Spain IMDEA Networks Inst Avda Mar Mediterraneo 22 Madrid 28918 Spain

Guaranteeing the eventual execution of tasks in machines that are prone to unpredictable crashes and restarts may be challenging, but is also of high importance. things become even more complicated when tasks arrive dynamically and have different computational demands, i.e., processing time (or sizes). In this paper, we focus on the online task scheduling in such systems, considering one machine and at least two different task sizes. More specifically, algorithms are designed for two different task sizes while the complementary bounds hold for any number of task sizes bigger than one. We look at the latency and 1-completed load competitiveness properties of deterministic scheduling algorithms under worst-case scenarios. For this, we assume an adversary, that controls the machine crashes and restarts as well as the task arrivals of the system, including their computational demands. More precisely, we investigate the effect of resource augmentation-in the form of processor speedup-in the machine's performance, by looking at the two efficiency measures for different speedups. We first identify the threshold of the speedup under which competitiveness cannot be achieved by any deterministic algorithm, and above which there exists some deterministic algorithm that is competitive. We then propose an online algorithm, named , that achieves both latency and 1-completed-load competitiveness when the speedup is over the threshold. this also proves that the threshold identified is also sufficient for competitiveness.

关键词： scheduling Online algorithms Task sizes Adversarial failures Resource augmentation Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Open Shop scheduling with Synchronization

引用

JOURNAL OF scheduling 2017年第6期20卷 557-581页

作者： Weiss, C. Waldherr, S. Knust, S. Shakhlevich, N. V. Univ Leeds Sch Comp Leeds LS2 9JT W Yorkshire England Univ Osnabruck Inst Comp Sci D-49069 Osnabruck Germany

In this paper, we study open shop scheduling problems with synchronization. this model has the same features as the classical open shop model, where each of the n jobs has to be processed by each of the m machines in an arbitrary order. Unlike the classical model, jobs are processed in synchronous cycles, which means that the m operations of the same cycle start at the same time. Within one cycle, machines which process operations with smaller processing times have to wait until the longest operation of the cycle is finished before the next cycle can start. thus, the length of a cycle is equal to the maximum processing time of its operations. In this paper, we continue the line of research started by Wei et al. (Discrete Appl Math 211:183-203, 2016). We establish new structural results for the two-machine problem with the makespan objective and use them to formulate an easier solution algorithm. Other versions of the problem, with the total completion time objective and those which involve due dates or deadlines, turn out to be NP-hard in the strong sense, even for machines. We also show that relaxed models, in which cycles are allowed to contain less than m jobs, have the same complexity status.

关键词： Open shop Synchronization Complexity

来源：评论

学校读者我要写书评

暂无评论

An Improved Quantum Particle Swarm Optimization and its Application 6

An Improved Quantum Particle Swarm Optimization and its Appl...

引用

6th International Conference on Computer Science and Network Technology (ICCSNT)

作者： Xuan, Jiao Ming, Huang Dalian Neusoft Univ Informat Dept Informat Management Dalian Peoples R China Dalian Jiaotong Univ Inst Software Dalian Peoples R China

ISBN: (纸本)9781538604939

Compared to other intelligent optimization algorithms, Quantum Particle Swarm Optimization (QPSO) possesses the characteristics like rapid convergence rate and outstanding global optimization performance etc. It is more applicable to solve workshop scheduling problems. the article proposes the strategy of improved dynamic reglation of rotation angle to solve multi-objective FJSP problems on the basis of Quantum Particle Swarm Optimization. the method can ensure the position with large variation of adaptive value not over optimal regulation measure, increase the capability to search optimal solution at the position with small variation of adaptive value, and verify the effectiveness of new algorithm through simulation experiement.

关键词： Quantum Particle Swarm Optimization (QPSO) flexible job-shop scheduling problem

来源：评论

学校读者我要写书评

暂无评论

Evolutionary Computation for the ARIEL mission planning tool 6

Evolutionary Computation for the ARIEL mission planning tool

引用

6th IEEE International Conference on Space Mission Challenges for Information Technology (SMC-IT)

作者： Garcia-Piquer, Alvaro Morales, Juan C. Colome, Josep Ribas, Ignasi CSIC IEEC Inst Space Sci Campus UABC Can Magrans S-N Bellaterra 08193 Spain

ISBN: (纸本)9781538634622

the ARIEL mission main goal is the measurement of atmospheres of transiting planets. this requires the observation of two types of events: primary and secondary eclipses. In order to yield measurements of sufficient Signal-to-Noise Ratio to fulfill the mission objectives, the events of each exoplanet have to be observed several times. In addition, several criteria have to be considered to carry out each observation, such as the exoplanet visibility, its event duration, its potential significance in the survey, and no overlapping with other tasks. Consequently, obtaining a long term mission plan becomes unaffordable for human planners due to the complexity of computing the huge number of possible combinations for finding an optimum solution. In this contribution we present a mission planning tool based on Evolutionary algorithms, which are focused on solving optimization problems such as the planning of several tasks. Specifically, the proposed tool finds a solution that highly optimizes the defined objectives, which are based on the maximization of the time spent on scientific observations and the scientific return. the results obtained on the large experimental set up support that the proposed scheduler technology is robust and can function in a variety of scenarios, offering a competitive performance which does not depend on the collection of exoplanets to be observed.

关键词： Space applications Observatory operations scheduling planning Evolutionary algorithms Constraint-based reasoning

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：