共查询到20条相似文献，搜索用时 281 毫秒
1.
Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications.
For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task
arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine
scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems
are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further
information about the tasks is available, which allows the improvement of the performance of the best possible algorithms.
Problems of this class are called semi-online ones. In this paper, the semi-online problemP2|decr|l
p (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum
of thel
p norm of every machine's load. It is shown thatLS algorithm is optimal for anyl
p norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problemsP2|online|l
p andP2|decr|l
p are presented.
Project supported by the National Natural Science Foundation of China (Nos. 10271110, 10301028) and the Teaching and Research
Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China 相似文献
2.
The combination of online or semi-online with deterioration jobs has never been researched in scheduling problems. In this paper, two semi-online parallel machine scheduling problems with linear deterioration processing time are considered. In the first problem, it is assumed that the deterioration rates of jobs are known in an interval, that is, bj ∈[0, α], where 0 〈α≤ 1 and bj denotes the linear deterioration rate. In the second problem, it is assumed that the largest deterioration rate of jobs is known in advance, that is, b = max1≤j≤n {bj }. For each of the two problems, a heuristic MBLS algorithm is worked out and its worst-case ratio is analyzed. At the same time, the worst-case ratio of the list （LS） algorithm is investigated and it is proved that all the ratios are tight. 相似文献
3.
黄宜坤 《临沂师范学院学报》2006,28(6):20-23
主要研究关于工件加工时间恶化的若干问题,给出了最大完工时间问题的一些性质、总完工时间问题的算法和性质,并根据实际问题,设计了一些新模型,相应地给出了该问题所具有的性质及一些简单算法． 相似文献
4.
为了研究更具实际意义的带有位置依赖影响的分组调度决策问题,建立了一般性位置依赖的分组调度模型.在模型中,分组实际发动时间和工件的实际加工时间被表示成初始时间和调度位置的一般函数.此类函数没有被假设为特殊函数形式,且没有要求限制其函数单调性.通过数理逻辑分析和证明,把所研究的问题模型分解为组调度过程和工件调度过程,并把每个调度过程分别转化为经典任务分派问题和单机排序调度问题,进而分析问题求解的计算复杂度.研究表明,即使在一般性位置依赖的模型假设下,单机最小化时间表长的分组调度问题和平行机最小化总负荷的分组调度问题仍然是多项式可解的. 相似文献
5.
在现代生产管理中,合理安排工件的加工顺序使所有的工件准时完工极为重要．文中研究工件不允许拖期的单机分批调度问题,目标是使加工．总成本最小,目标函数不仅考虑了工件提前完工有提前惩罚成本,还考虑了批加工成本费用．提出了一种多项式时间的最优算法． 相似文献
6.
混部负载是当前业界提高数据资源利用率的重要手段,其原理是将在线负载和离线负载共同放置于同一数据中心、共享资源,在保证在线负载服务质量的前提下,将空闲资源分配给离线负载。当前针对混部负载中离线负载的资源调度采用传统的公平或者短作业优先等策略,并未考虑在线负载资源需求波动对离线负载运行的影响。为了达到进一步提升资源利用率和作业吞吐率的目的,提出基于负载完成时间预判的模拟退火资源分配策略。结果表明,该策略比公平策略和短作业优先策略在平均资源利用率上分别提高了7.8%和15.5%,在吞吐率上分别提高了38.2%和29.1%。 相似文献
7.
关于简单线性恶化问题的平行机排序的一个全多项式逼近算法 总被引：1，自引：0，他引：1
In this paper, a parallel machine scheduling problem was considered , where the processing time of a job is a simple linear function of its starting time. The objective is to minimize makespan. A fully polynomial time approximation scheme for the problem of scheduling n deteriorating jobs on two identical machines was worked out. Furthermore, the result was generalized to the case of a fixed number of machines. 相似文献
8.
Optimal online algorithms for scheduling on two identical machines under a grade of service 总被引：8，自引：0，他引：8
INTRODUCTIONWe study the problem of online scheduling on two identical parallel machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels. The goal is to minimize the makespan under the constraint that all requests are satisfied. This problem was first proposed by Hwang et al.(2004) and is motivated by the following scenario. In the service industry, the service providers often have special customers, such as, go… 相似文献
9.
对有限个固定工件,n个自由工件的单机排序问题1｜FB（F）｜max wjCj进行了研究,证明该问题在F≥2的情况下不存在最坏性能比为2n的多项式时间近似算法;对只有一个固定工件,（maxwi1≤i≤n）/（minwi1≤i≤n）=c与输入无关的情形,设计了时间界为O（2c/εn＋nlogn）的多项式时间近似方案. 相似文献
10.
This paper considers a reentrant scheduling problem on parallel primary machines with a remote server machine, which is required to carry out the setup operation. In this problem, each job has three operations. The first and last operations are performed by the same primary machine, implying the reentrance, and the second operation is processed on the single server machine. The order of jobs is predetermined in our context. The challenge is to assign jobs to the primary machines to minimize the makespan. We develop a genetic algorithm（GA） to solve this problem. Based on a simple strategy of assigning jobs in batches on the parallel primary machines, the standardized random key vector representation is employed to split the jobs into batches. Comparisons among the proposed algorithm, the branch and bound（BB） algorithm and the heuristic algorithm, coordinated scheduling（CS）, which is only one heuristic algorithm to solve this problem in the literature, are made on the benchmark data. The computational experiments show that the proposed genetic algorithm outperforms the heuristic CS and the maximum relative improvement rate in the makespan is 1.66%. 相似文献
11.
In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off-line or on-line
environment. But in practice, problems are often not really off-line or on-line but somehow in between. This means that, with
respect to the on-line problem, some further information about the tasks is available, which allows the improvement of the
performance of the best possible algorithms. Problems of this class are called semi on-line ones. The authors studied two
semi on-line multiprocessor scheduling problems, in which, the total processing time of all tasks is known in advance, or
all processing times lie in a given interval. They proposed approximation algorithms for minimizing the makespan and analyzed
their performance guarantee. The algorithms improve the known results for 3 or more processor cases in the literature.
Project supported by the National Natural Science Foundation of China (Nos. 19701028 and 19971078) and National 973 Research
Project of China. 相似文献
12.
We consider a scheduling problem involving a single processor utilized by two customers with constant deteriorating jobs,i.e.,jobs whose processing times are an increasing function of their starting times.Traditionally,such scenarios are modeled by assuming that each customer has the same criterion.In practice,this assumption may not hold.Instead of using a single criterion,we examine the implications of minimizing an aggregate scheduling objective function in which jobs belonging to different customers are evaluated with their individual criteria.We examine three basic scheduling criteria:minimizing makespan,minimizing maximum lateness,and minimizing total weighted completion time.We demonstrate all the scheduling problems considered are polynomially solvable. 相似文献
13.
黄艳 《深圳信息职业技术学院学报》2021,(1)
高校思想政治理论课长久以来面临三个棘手问题,即“出勤率低”“听课率低”“抬头率低”,传统的线下教学容易出现“单向灌输”的弊端。由于疫情大规模出现的单一线上教学则易导致学习效率低、学习目的盲目等问题。后疫情时代,高校思想政治理论课教师进行新型的线上线下混合式教学模式的改革势在必行。线上线下混合式教学模式具有多维性、灵活性、多样性、实践性等优点,有助于提高学生学习兴趣,解决课堂三大难题,回归课堂立德树人的本质。线上线下混合式教学模式的改革创新应从以下方面着手:创建及完善与之对应的信息和教育平台;开发与之相配合的电子资料和工具;注重提高学生的独立研究能力及创造能力;推进考核形式的改革和创新;确保网络意识形态安全。 相似文献
14.
本文研究两台平行同类机的一个半在线排序问题。当机器是有准备时间的同类机时,总加工时间已知,文章给出了一个竞争比至少为的半在线算法,同时给出了证明。 相似文献
15.
16.
In this paper we consider an online scheduling of parallel jobs with preemption on identical machines, where jobs arrive over time. The objective is to minimize the makespan. For the problem that jobs have only two possible widths mj = 1 or m, we present an optimal online algorithm by using ＂temporary schedule＂. 相似文献
17.
研究预防性周期维护策略下再制造系统中可中断和不可中断2类工件的单机调度问题.以最小化完工时间为目标,提出了LPT-LS算法,该算法首先按LPT(longest processing time)规则安排不可中断工件,然后按LS(list scheduling)规则安排可中断工件.并根据可中断工件的总加工时间(记为S2)分3种情况证明了该算法的最坏情况比,结论如下:当S2大于按LPT规则安排不可中断工件后机器的空闲时间时,最坏情况比为1;当S2介于分别按LPT规则和OPT(最优排序)规则安排不可中断工件后机器的空闲时间之间时,最坏情况比小于2;当S2小于按OPT规则安排不可中断工件后机器的空闲时间时,最坏情况比小于2.最后通过算例验证了结论的正确性. 相似文献
18.
徐聪 《中国现代教育装备》2022,(3):71-73
分析了线上实验教学的必要性,探索了机械原理实验教学模式.根据不同实验的特点分别采用线上实验教学模式和线上线下混合式实验教学模式,给出了具体的教学方案,并分析了线上实验教学存在的问题.该实验教学模式为今后的实验教学开拓了新思路,提供了参考. 相似文献
19.
受新型冠状肺炎疫情影响,"PLC原理及应用"课程的教学需要从线下转为线上进行。该文针对实验教学环节,在深度分析传统线下硬件平台实验教学的优缺点、PLC控制器的工业应用属性及实验教学内容与目标等基础上,提出将与典型PLC控制器产品相配套的工业应用软件TIA和PLCSIM作为仿真实验工具,并设计了难度进阶合理的实验内容。教学实践表明,线上实验教学提高了学生学习的自主性,锻炼了学生分析和解决实际问题的能力,显著提升了学生对相关工业软件的实操能力,达到了实验教学目标要求,并为日后继续进行线上或线上线下相结合的教学实践打下了坚实基础。 相似文献
20.
线上线下混合式教学模式是教育部确定的五类国家级一流本科课程类型之一。为解决“环境影响评价”课程传统线下教学中的难点问题,在课程教学中开展线上线下混合式教学改革与实践。构建了“课前预习+课中研习+课后复习”的线上线下混合式教学模式,包括课前知识传递、课中知识内化、课后知识提升三个环节。在教学实践中以问题为导向、以学生为中心,融合了课程思政、线上导学、翻转课堂、案例分析、小组辩论、模拟仿真、过程考核等多种教学方法,在教学内容、教学资源和教学方法方面形成了鲜明特色。学生成绩纵向比较结果表明,教学改革效果良好,为高校“线上线下混合式一流课程”建设提供参考。 相似文献