作业调度问题
实验六：作业调度问题
一、实验目的与要求
1、作业调度问题的算法
2、掌握贪心算法
二、实验题：
问题描述：要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。
[实验提示]
1)把作业按加工所用的时间从大到小排序；
2)如果作业数目比机器的数目少或相等，则直接把作业分配下去；
3)如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。
#include
using namespace std;
void Greedy(int t[],int n,int m);
int main() {
int n=7,m=3,t[]={2,14,4,16,6,5,3};//待分配的工作
Greedy(t,n,m);
return 0; }
void Greedy(int t[],int n,int m)
{ int flagn,flagm; int M[]={0,0,0,0,0,0,0,0};
for(int i=0;i { int max=0,min=10000; flagn=0; flagm=0; for(int j=0;j { if(max for(j=0;j { if(M[flagm]>M[j]) {flagm=j;} } M[flagm]=M[flagm]+t[flagn]; t[flagn]=0; //被选择过的机器时间调为 0 cout< 12.假设一个系统中有5个进程，它们到达的实践依次为0、2、4、6、8，服务时间依次为3、6、4、5、2，忽略I/O以及其他时间开销，若分别按响应比高者优先、时间片轮转（时间片为1）、先来先服务、非抢占短进程优先、抢占短进程优先调度算法调度CPU，请给出进程的调度顺序，计算各进程的平均周转时间和平均带权周转时间。 【解】 （1）响应比高者优先调度算法 平均周转时间=（3+7+9+14+7）/5 = 40/5 = 8 平均带权周转时间=(1+1.17+2.25+2.8+3.5)/5=10.72/5=2.144 （2）时间片轮转（时间片为1）调度算法 平均带权周转时间=(1+2.67+2.75+2.8+4)/5=13.22/5=2.644 进程调度顺序：P1、P2、P3、P4、P5 平均周转时间=（3+7+9+12+12）/5 = 41/5 = 8.2 平均带权周转时间=(1+1.17+2.25+2.4+6)/5=12.82/5=2.564 （4）非抢占短进程优先调度算法 平均周转时间=（3+7+11+14+3）/5 = 38/5 = 7.6 平均带权周转时间=(1+1.17+2.75+2.8+1.5)/5=9.22/5=1.844 （5）抢占短进程优先调度算法 平均周转时间=（3+18+9+9+2）/5 = 41/5 = 8.2 平均带权周转时间=(1+3+2.25+1.8+1)/5=9.05/5=1.81 补充：有5个待运行的进程A、B、C、D、E，各自估计运行时间为9、6、3、5、x，试问哪种运行次序可以使平均响应时间最短？ 【解】 使平均响应时间最短的调度算法是短进程优先。因进程E的时间待定，所以调度次序与x 的大小有关。 （1）当x<3时的运行次序为：E、C、D、B、A （2）当3<=x<5时的运行次序为：C、E、D、B、A （3）当5<=x<6时的运行次序为：C、D、E、B、A （4）当6<=x<9时的运行次序为：C、D、B、E、A （5）当x>=9时的运行次序为：C、D、B、A 、E 一、二维背包问题 一维背包问题讨论的背包问题只有一种限制，即旅行者所能承受的背包的重量（亦即重量不能超过a （kg ）.但是实际上背包除受重量的限制外，还有体积的限制，这就是不但要求旅行者的背包的重量M 不能超过a （kg ），还要求旅行者背包的体积V 不能超过b （m3）,我们把这样的问题称为“二维背包问题”。 它的状态变量有两个因素:一个是重量，一个是体积。 二维背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i 件物品所需的两种代价分别为i a 和i b 。两种代价可付出的最大值（两种背包容量）分别为a 和b 。物品的价值为i c 。 模型： 11 1 max . ,1,2,3...n i i i n i i i n i i i i c x st a x a b x b x z i n ===≤≤∈=∑∑∑ 例题 码头有一艘载重量为30t ，最大容为12×10m 3的船，由于运输需要,这艘船可用于装载四种货物到珠江口，它们的单位体积,重量及价值量见下表: 现求如何装载这四种货物使价值量最大。 1 1 1 max .,1,2,3...n i i i n i i i n i i i i c x st a x a b x b x z i n ===≤≤∈=∑∑∑ 可用动态规划来解决 1.设x i （i=1,2,3,4）分别表示装载这四种货物的重量， 2.阶段k ：将可装入的货物按1,2,3,…n 排序，每个阶段装一种货物，（共可分为四个阶段） 3.状态变量： 1k S +和1k R +，表示在第k 阶段开始时，允许装入的前k 种货物的重量与体积。 状态转移方程： 11k k k k k k k k S S a x R R b x ++=-=- ()(){}111,max ,j k k j k k j j f S R f S R c x -++=+，表示在不超过重量和体积的前提下，装 入前j 中货品的价值。（j=1,2,3,4） 源代码： #include 基于WSA算法的作业车间低碳调度方法研究 1.1 引言 本章主要研究了以最大化完工时间和能耗指标为目标的作业车间低碳调度模型的求解方法。首先，建立了多目标作业车间低碳调度模型；然后基于Pareto 支配理论，设计了一种高效的MODWSA算法获得满意的Pareto非支配解；最后，设计了一套测试算例，将MODWSA算法与其它经典多目标算法进行比较分析，验证了MODWSA算法的优越性。在本研究中，作者完成了两项工作：首先，构建了一个新的多目标作业车间低碳数学模型；其次，设计了一种高效的MODWSA算法获得满意的Pareto非支配解。 1.2 作业车间低碳调度模型 本章研究的作业车间低碳调度问题可描述如下：对给定的n个工件及k台机器，一个工件的加工需要经过m道工序，每道工序允许在特定的机器上加工，任意一台机器在任意一个时刻仅能加工某一工件的某一道工序，并且一个工件只能在其上道工序完成后下一道工序才能开始加工[插入文献]。 考虑机器的准备时间，准备时间与同一机器上相邻两工件的加工顺序相关，并且机器的启动和工件的加工是相连的。对应于不同工序，机器具有不同的速率档位进行加工，并且可以进行调节。从能耗的角度来看，机器有四种不同的状态：加工状态(机器在加工工件)，启动状态（机器在准备加工一个新的工件），待机状态（机器处于空转中），以及关机状态（机器被关机）。通常情况下，当机器在较高速率运作时，工件的加工时间会被缩短，但是相应的能耗会增加。因此本问题以最大化完工时间和能耗指标为目标，由于本章所研究问题的特点，该问题要比传统的作业车间调度问题要复杂的多。在该问题中，其它设定如下： ●工件在车间里被连续加工。也就是说，加工过程不能被中断。 ●机器允许有空闲时间，并且各阶段间具有容量无限的缓冲区。 ●当有第一个工件在机器上加工时，机器开机；当在该机器上加工的所有工件 加工完毕后，机器关机。 ●机器速度在工件加工过程中不能进行调整。 1.2.1 混合整数规划模型 为了提出问题的数学模型，根据上面对问题的描述，我们首先定义了下面的相关数学符号。 《操作系统》实验报告 题目：作业调度算法 班级：网络工程 姓名：朱锦涛 学号：E31314037 一、实验目的 用代码实现页面调度算法，即先来先服务（FCFS）调度算法、短作业优先算法、高响应比优先调度算法。通过代码的具体实现，加深对算法的核心的理解。 二、实验原理 1.先来先服务（FCFS）调度算法 FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。 2.短作业优先算法 SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存。 3、高响应比优先调度算法 高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理机调度的性能。 如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可以描述为： 优先权 = （等待时间 + 要求服务时间）/要求服务时间 三、实验内容 源程序： #include 作业调度实验报告 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT 实验二作业调度 一.实验题目 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 （1）先来先服务算法：按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。 （2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准，总是优先选取执行时间最短的作业。 （3）响应比高者优先算法：是在每次调度前都要计算所有被选作业（在后备队列中）的响应比，然后选择响应比最高的作业执行。 2、编写并调度一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法进行设计。 对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。 二.实验目的： 本实验要求用高级语言（C语言实验环境）编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解三 .实验过程 <一>单道处理系统作业调度 1)单道处理程序作业调度实验的源程序: 执行程序: 2)实验分析： 1、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU 时限等因素。 2、每个作业由一个作业控制块JCB 表示，JCB 可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W 。 3、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间。 3)流程图: 二.最短作业优先算法 三.高响应比算法 图一.先来先服务流程图 4)源程序: #include <> #include <> #include <> #define getpch(type) (type*)malloc(sizeof(type)) #define NULL 0 int n; float T1=0,T2=0; int times=0; struct jcb .\n",p->name); free(p); .wait...",time); if(times>1000) 代替 代替 调度员职责范围、工作标准、作业程序 一、调度员职责范围 （一）机车调度员岗位职责范围 １、机车调度员 （１）领导全组人员严格遵章守纪，认真执行各项规章制度，认真了解机统一上班存在问题，根据天、地、人、时订出保证和预想，做到有记录、有正式台帐对照规章命令，指示及段细日班计划，机车周转图组织供质量良好的机车，组织及时整备正点出库，禁止放出违背（技规）第113条规定的机车，根据机车实际运用情况向调度提出合理化建议和要求，经济合理的运用机车，提高机车运用效率，对客车特别担当有重要任务的机车，班长应亲自检查机车并督促正点出库。 （２）按照机车检修、计划，司机途中预报掌握活件情况，根据轻重缓急，积极组织调正机车入库或组织派人积极抢修，并督促指导司机途中正确处理紧急活件，安全回段修理，10点参加洗检碰头会向工厂检修部门重点汇报运用问题和建议，掌握小辅修;中检、临修机车的交路计划，及时准确填写各种报表及机车小辅修走行公里和划清小辅修符号，正确填写机统一等台帐记录。 （３）了解出入厂机车的回送状态，督促机车的过境回送工作。 （４）督促做好机车整备工作，检查库内停留机车的防溜、防冻作业，重点检查特、专、军运、客机车、备用检修加入运用的机车，对运行中的安全问题和事故情况及时查明原因通知值班人员和有关领导果断采取措施，不得延误。 （５）督促检查本班调度员的标准化作业程序和班组建议，严格执行考勤制度和各种学习制度，做好人员的岗位思想工作。 （６）主持本班碰头会，听取领导有关指示、布置班中工作，传达有关注意、安全事项。 （７）参加交班会，详细向领导汇报机车出段和运行正点，行车安全、机车质量、定检机车出、入库时间、主要指标完成情况、上级指示贯彻执行情况、好人好事以及提出改正工作意见。 ２、调度员（人事） （１）加强对机车乘务员的管理，严格掌握固定包车制及轮乘制，严格纪律，根据计划按时准确的派班、叫班，合理使用人员。 （２）掌握乘务员考勤，办理各种假的请假手续和旷工、漏乘登记，对各种假要正确挂牌，不得有私情、舞弊行为，做好岗位思想工作。 （３）严格控制和按段文件规定的便乘票使用办法，必须认真保管、回收、发放，不得超范围使用。（４）负责叫班工作，校对计划准确，派班、做到三对照，四不叫、不早叫、不晚叫、不漏叫、不错叫，对过境回送机车派线路指导。负责电子与人名牌维护确保准确无误. （５）维护固定包乘组，需要打乱的由主任批准，若有替班人员时应事先有计划的配好班次，防止三人同时替班，确保人身和行车安全正点。 （６）交班要实行对口交接，接班人员未到，交班人员不得擅自离开工作岗位，将交班四小时工作安排好，认真填写交班记录，并将有关命令、电报、文件、上级指示及未完成工作向接班人员交待清楚。（７）参加交班会向领导汇报人员动态，恢复包乘组等情况，认真执行标准化作业情况。 ３、计划调度员 （１）及时收抄上级命令和指示，审查校对日班计划，落实交接班机车实际位置后的机车交路实现，按 作业调度 一、实验目的 1、对作业调度的相关内容作进一步的理解。 2、明白作业调度的主要任务。 3、通过编程掌握作业调度的主要算法。 二、实验内容及要求 1、对于给定的一组作业, 给出其到达时间和运行时间，例如下表所示： 2、分别用先来先服务算法、短作业优先和响应比高者优先三种算法给出作业的调度顺序。 3、计算每一种算法的平均周转时间及平均带权周转时间并比较不同算法的优劣。 测试数据 workA={'作业名':'A','到达时间':0,'服务时间':6} workB={'作业名':'B','到达时间':2,'服务时间':50} workC={'作业名':'C','到达时间':5,'服务时间':20} workD={'作业名':'D','到达时间':5,'服务时间':10} workE={'作业名':'E','到达时间':12,'服务时间':40} workF={'作业名':'F','到达时间':15,'服务时间':8} 运行结果 先来先服务算法 调度顺序:['A', 'B', 'C', 'D', 'E', 'F'] 周转时间: 带权周转时间: 短作业优先算法 调度顺序:['A', 'D', 'F', 'C', 'E', 'B'] 周转时间: 带权周转时间:1. 响应比高者优先算法 调度顺序:['A', 'D', 'F', 'E', 'C', 'B'] 周转时间: 带权周转时间: 五、代码 #encoding=gbk workA={'作业名':'A','到达时间':0,'服务时间':6,'结束时间':0,'周转时间':0,'带权周转时间':0} workB={'作业名':'B','到达时间':2,'服务时间':50} workC={'作业名':'C','到达时间':5,'服务时间':20} workD={'作业名':'D','到达时间':5,'服务时间':10} workE={'作业名':'E','到达时间':12,'服务时间':40} workF={'作业名':'F','到达时间':15,'服务时间':8} list1=[workB,workA,workC,workD,workE,workF] list2=[workB,workA,workC,workD,workE,workF] list3=[workB,workA,workC,workD,workE,workF] #先来先服务算法 def fcfs(list): resultlist = sorted(list, key=lambda s: s['到达时间']) return resultlist #短作业优先算法 def sjf(list): time=0 resultlist=[] for work1 in list: time+=work1['服务时间'] listdd=[] ctime=0 for i in range(time): for work2 in list: if work2['到达时间']<=ctime: (work2) if len(listdd)!=0: li = sorted(listdd, key=lambda s: s['服务时间']) (li[0]) (li[0]) ctime+=li[0]['服务时间'] listdd=[] -- 月报表调度作业 BEGIN TRANSACTION DECLARE @JobID BINARY(16) DECLARE @ReturnCode INT SELECT @ReturnCode = 0 IF (SELECT COUNT(*) FROM msdb.dbo.syscategories WHERE name = N'[Uncategorized (Local)]') < 1 EXECUTE msdb.dbo.sp_add_category @name = N'[Uncategorized (Local)]' -- 删除同名的警报（如果有的话）。 SELECT @JobID = job_id FROM msdb.dbo.sysjobs WHERE (name = N'TestJob') IF (@JobID IS NOT NULL) BEGIN -- 检查此作业是否为多重服务器作业 IF (EXISTS (SELECT * FROM msdb.dbo.sysjobservers WHERE (job_id = @JobID) AND (server_id <> 0))) BEGIN -- 已经存在，因而终止脚本 RAISERROR (N'无法导入作业“TestJob”，因为已经有相同名称的多重服务器作业。', 16, 1) GOTO QuitWithRollback END ELSE -- 删除［本地］作业 EXECUTE msdb.dbo.sp_delete_job @job_name = N'TestJob' SELECT @JobID = NULL END BEGIN -- 添加作业 EXECUTE @ReturnCode = msdb.dbo.sp_add_job @job_id = @JobID OUTPUT , @job_name = N'TestJob', @owner_login_name = N'Machine1\Admin', @description = N'没有可用的描述。', @category_name = N'[Uncategorized (Local)]', @enabled = 1, @notify_level_email = 0, @notify_level_page = 0, @notify_level_netsend = 0, @notify_level_eventlog = 2, @delete_level= 0 IF (@@ERROR <> 0 OR @ReturnCode <> 0) GOTO QuitWithRollback -- 添加作业步骤 EXECUTE @ReturnCode = msdb.dbo.sp_add_jobstep @job_id = @JobID, @step_id = 1, @step_name = N'Exec GenerateMothlyReport_Proc', @command = N'Exec GenerateMothlyReport_Proc', @database_name = N'master', @server = N'', @database_user_name = N'', @subsystem = N'TSQL', @cmdexec_success_code = 0, @flags = 0, @retry_attempts = 0, @retry_interval = 1, @output_file_name = N'', @on_success_step_id = 0, @on_success_action = 1, @on_fail_step_id = 0, @on_fail_action = 2 IF (@@ERROR <> 0 OR @ReturnCode <> 0) GOTO QuitWithRollback 作业调度实验报告 1、实验目的 作业管理是用户与操作系统的接口。作业调度的主要功能是检查系统是否能满足用户作业的资源要求以及按照一定的算法选取作业。 本实验的目的是通过模拟作业调度算法的设计加深对作业管理基本原理的理解。 2 实验用具 个人电脑 3、实验内容 ⑴在后备作业队列中，输入5个作业的名称、状态、就绪时间、服务时间及存储空间。 ①按先来先服务的原则进行调度，输出作业调度的顺序及等待的时间。 ②按最短作业（即运行时间最短）优先的原则进行调度，输出作业调度的顺序及等待时间。 4 实习步骤 第一步：首先对整个题目进行分析，包括对作业、主存的定义类型。 第二步：对流程图进行分析，分析一些细节代码。 第三步：根据程序流程图写代码并调节一些细节错误。 第四步：运行看结果，这里主要看内存根据作业的要求对分配情况。 4.1 需求分析 本次实验是在预输入五道作业的基础上初始化，并通过作业的需求更改主存的输出显示情况，首先是输入5道作业，分别使用先来先服务算法和最短时间优先算法分配内存，最后进行内存的回收。 4.2 数据结构设计与说明 定义作业中的变量-资源需求： typedef struct source { int size; //资源要求大小 int tape_count; //资源要求磁带数 }src; 定义作业： typedef struct jobwork { char username[10]; //用户名 char jobname[10]; //作业名 char state[5]; //运行状态 int runtime; //运行时间 src source; //资源需求（结构体类型见上） struct jobwork *next; //下一个指针 }job; 定义内存： typedef struct memory { int size; //内存大小 int tape_count; //内存磁带数 char jobname[10]; //内存中存在的作业名（首次为空） char username[10]; //内存中作业的用户名char state[5]; //内存中作业的状态 int job_count; //内存中作业个数struct memory *next; //内存下一个指针}mem; 4.3 算法设计 第一部分：初始化作业表 第15卷第7期计算机集成制造系统 Vol.15No.72009年7月 Computer Integrated Manufacturing Systems July 2009 文章编号:1006-5911(2009)07-1383-06 收稿日期:2008 06 18;修订日期:2008 10 13。Received 18June 2008;accepted 13Oct.2008. 基金项目:国家自然科学基金资助项目(70771008,70371057)。Fo undation item:Project supp orted by the National Natural Science Fundation, Ch ina(N o.70771008,70371057). 作者简介:崔健双(1971-),男,河北衡水人,北京科技大学经济管理学院副教授,博士,主要从事生产调度算法理论及应用、安全电子商务的研 究。E mail:cuijs@manag https://www.wendangku.net/doc/e718359607.html, 。 求解作业车间调度问题的全局邻域搜索方法 崔健双,李铁克 (北京科技大学经济管理学院,北京 100083) 摘 要:采用传统的关键邻域搜索方法求解作业车间调度问题时,往往容易陷入局部极值而且难以跳出。为此,提出了一种具有动态调整能力的全局邻域交换策略,该策略有可能产生大量的不可行调度,需要一种筛选方法加以过滤。证明了一个新的邻域交换性质,利用该性质可以对所得调度方案作可行性约束判定,从而有效地过滤掉不可行调度。在此基础上,提出了一种求解作业车间调度问题的算法。最后,取不同规模的Benchmar k 问题算例对该算法进行测试,结果表明,无论从解的质量还是计算时间都取得了较好的效果。 关键词:邻域结构;关键路径;作业车间调度;邻域交换;调度算法中图分类号:T P18 文献标识码:A Global neighborhood algorithm for Job Shop scheduling problem CUI J ian shuang,LI T ie ke (Scho ol of Economic M anag ement,U niversit y of Science &T echno lo gy Beijing,Beijing 100083,China)Abstract:T r aditional cr itical neighbor ho od alg or ithms fo r Jo b Shop scheduling problem w ere easily t rapped into local optimal and hardly to escape.T o deal w ith t his pro blem,a g lo bal neig hbo rhoo d swapping st rateg y wit h dynamic adapatability w as pr oposed.H ow ever,this new strateg y mig ht possibly induce infeasible so lutio ns.T hus,a new pr oposition concerning the neig hbor hood sw apping str ategy w as presented and pr ov ed,w hich could be used to v erify whether a neighbor ho od swapping w as accept able or not.Based on this g lo bal neig hbo rhoo d st rateg y,a new alg o r ithm w as develo ped and tested by a gr oup of benchmark instances.T he r esults indicated that the new algo rithm ob tained satisfactor y results both on solut ions quality and computat ion time. Key words:neig hbo rhoo d structur e;crit ical path;Job Sho p scheduling ;neighborho od sw apping;scheduling alg o rithms 0 引言 自从20世纪50年代以来,调度问题相关理论及其应用技术的研究已经发展成为一门重要的学科,从经典的单机调度、并行机调度、车间调度发展到后来的多目标调度、随机调度和模糊调度等内容。调度问题成为从事运筹学、人工智能学和应用数学等学科领域的学者们关注的焦点,相应的应用领域在不断地扩大。随着问题研究的深化,人们对解决 调度问题的难度有了进一步的认识,发展了关于调度算法的有效性和计算复杂性理论,并且证明出许多调度问题包括多数作业车间调度问题(Jo b Shop Scheduling Problem,JSP)都是NP 完备问题[1]。JSP 是利用一组有限资源对一批有限任务在满足给定约束条件下求解最优目标函数的一个复杂的组合优化问题,也是迄今为止人们研究最多、研究成果最丰富、但仍未得到根本解决的问题之一。事实表明,有些NP 完备问题存在有限时间内的可行解, 制造业车间作业计划与调度研究 车间作业计划（Production Activity Control，PAC）是依据主生产计划（MPS）而编制的具体执行工作方案，它把车间的生产任务落实到每个人、每台设备上，是车间组织生产的依据，也是企业管理中最重要的部分。PAC的实施贯穿于生产系统的各道工序，受很多因素的制约。随着生产规模的扩大和复杂程度的提高，PAC的实施与调度也出现了一些问题。本文应用车间作业调度方法，针对当前PAC与调度中存在的问题进行研究，为企业提供优化的生产作业排序和车间作业调度策略，从实践与理论方面提升PAC及其调度水平，以提高制造系统的运行效率，增强企业的市场竞争力。 PAC与车间调度的内涵与特点 PAC系统是一个高度复杂的系统，它有效地综合了机械、信息、网络等资源。制定PAC是为了使生产设备、物料、人员和信息四者匹配，实现车间均衡、协调、持续生产。在PAC生产执行过程中，决策部门需要根据车间的生产能力及其它资源的使用等反馈情况不断地调整PAC，而调整计划贯穿于企业生产活动的全过程。因此，要最大限度地发挥生产系统的柔性潜力，满足市场需求。 1.1 PAC与车间调度的界定与内涵 PAC的编制包括确定操作顺序、分配资源和制定期量标准等。PAC与车间调度问题是一个典型的任务集，包括资源集、约束条件集、性能指标集。其中，资源集包括人员、设备、工具和材料等，而每台设备可以完成一种或多种作业，不同设备能完成的作业集可能相同也可能不同；约束条件集用以规定生产过程中需要的条件，如任务的优先级、每个作业要求完成的时间、资源的能力、生产工艺、质量标准等；性能指标集用以规定生产过程中需要优化的目标，如生产周期、在制品量、订单交货期、资源利用率和生产成本等。每一个任务都包含一组需要执行的作业序列（工序），而这些作业序列需要占用系统的机器、工具等资源，并且必须按照一定的工艺顺序执行。 调度的目标是为作业合理分配资源，为每一个加工对象合理安排具体的加工顺序、路径、时间、制造设备资源和操作等，使内部和外部约束条件被满足，其中内部约束主要为企业的资源约束、能力约束和生产过程中的技术约束等；外部约束主要为订单规定的时间要求和品质要求等，同时使大部分生产性能指标得到优化。在有限产能、库存容量及资源的约束下，通过优化配置生产资源来提高PAC的可实施性以及生产过程的可计划性、可控性。而车间作业调度与控制则是实现生产高效率、高柔性和高可靠性的关键环节。 1.2 编制PAC的特点 在编制PAC过程中应考虑其如下特点： （1）实用性。以在制品加工进度为基础编制工序能力计划，使PAC紧跟生产现场，达到计划编制与生产节拍的和谐统一。PAC计划期短、计划内容具体、计划单位小等，具有可操作性强。 （2）合理性。综合上级计划、在制品进展情况、工序周期、工序时差和剩余工作量等因素，通过合理地排程方法，达到满足交付和有效利用资源的目的。 实验二作业调度 一.实验题目 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 （1）先来先服务算法：按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。 （2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准，总是优先选取执行时间最短的作业。 （3）响应比高者优先算法：是在每次调度前都要计算所有被选作业（在后备队列中）的响应比，然后选择响应比最高的作业执行。 2、编写并调度一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法进行设计。 对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。 二.实验目的： 本实验要求用高级语言（C语言实验环境）编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解 三 .实验过程 <一>单道处理系统作业调度 1)单道处理程序作业调度实验的源程序: 执行程序: 2)实验分析： 1、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU 时限等因素。 2、每个作业由一个作业控制块JCB 表示，JCB 可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W 。 3、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间。 3)流程图: 二.最短作业优先算法 三.高响应比算法 图一.先来先服务流程图 4)源程序: #include <> #include <> #include <> #define getpch(type) (type*)malloc(sizeof(type)) #define NULL 0 int n; 代替 代替 实习九作业调度 一、实习内容 模拟批处理多道操作系统的作业调度。 二、实习目的 每个用户请求计算机计算的一个计算任务叫做一个作业。一个作业从输入初始数据到得到计算结果，要经过若干个步骤的相继执行。例如，编辑、编译、运行等，其中每一个步骤称作一个作业步。用户向系统提出作业加工步骤的方式称作业控制方式，作业控制方式有两种：终端控制方式（又称直接控制方式或联机控制方式）和批处理控制方式（又称自动控制方式或脱机控制方式）。 在批处理控制方式下，用户采用系统提供的作业控制语言（JCL）写好作业说明书，说明作业加工的步骤。操作员把一批作业组织成输入流，通过“预输入”手段使每个作业的信息（包括作业说明书、源程序、初始数据等）暂存在辅助存储器的“输入井”中。 批处理多道操作系统的作业管理有两个任务：作业调度和作业控制。采用多道程序设计方法的操作系统，在系统中要经常保留多个运行的作业，以提高系统效率。作业调度从系统已接纳的暂存在输入井中的一批作业中挑选出若干个可运行的作业，并为这些被选中的作业分配所需的系统资源。对被选中运行的作业必须按照它们各自的作业说明书规定的步骤进行控制。 本实习要求学生模拟作业调度的实现，了解作业调度在操作系统中的作用。 三、实习题目 采用先来先服务算法和运行时间最短者优先算法模拟设计作业调度程序。 [提示]： (1) 作业调度程序负责从输入井选择若干个作业进入主存，为它们分配必要的资源，当它们能够被进程调度选中时，就可占用处理器运行。作业调度选择一个作业的必要条件是系统中现有的尚未分配的资源可满足该作业的资源要求。但有时系统中现有的尚未分配的资源既可满足某个作业的要求也可满足其它一些作业的要求，那么，作业调度必须按一定的算法在这些作业中作出选择。先来先服务算法是按照作业进入输入井的先后次序来挑选作业，先进入输入井的作业优先被挑选，当系统中现有的尚未分配的资源不能满足先进入输入井的作业时，那么顺序挑选后面的作业。运行时间最短者优先算法总是按作业要求运行的时间来选择作业，每次挑选要求运行时间短且资源要求能满足的作业先进入主存执行。 (2) 为了表示暂存在输入井中的各个作业的情况（作业信息在输入井中的位置、作业的资源要求等），常常采用二级目录结构：作业表和预输入表。例如： 作业表 “预输入” （源程序文件、数据文件等）登记在预输入表中。“预输入”程序工作时还把作业控制语句集中，作为作业说明书文件存放在输入井并登记在预输入表的第一栏中，同时把用户在作业说明书中提出的资源要求登记在作业表中。 本实习模拟作业调度，所以可不考虑有关“预输入”程序的工作。假定“预输入”程序 实验二作业调度实验 一. 目的要求： 用高级语言编写和调试一个或多个作业调度的模拟程序，以加深对作业调度算法的理解。 二. 例题：为单道批处理系统设计一个作业调度程序。 由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。 作业调度算法：采用先来先服务（FCFS）调度算法，即按作业提交的先后次序进行调度。总是首先调度在系统中等待时间最长的作业。 每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。 作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。 各个等待的作业按照提交时刻的先后次序排队，总是首先调度等待队列中队首的作业。 每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。 调度算法的流程图如下图所示。 三 . 实习题： 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业等待算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，以比较各种算法的优缺点。 2、编写并调度一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法进行设计。 对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。 3、编写并调试一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于优先级的作业调度。 可以参考课本中的例子自行设计。 三 . 实验过程： 1、编写并调试一个单道处理系统的作业等待模拟程序。 先来先服务（FCFS）： main.cpp: /* **先来先服作业调度算法模拟 */ #include 例题：为单道批处理系统设计一个作业调 度程序 由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作 业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU 时限等因素。 作业调度算法：采用先来先服务（FCFS）调度算法，即按作业提交的先后次序进行调度。总是首先调度在 系统中等待时间最长的作业。 每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需 的资源、作业状态、链指针等等。 作业的状态可以是等待W(Wait)、运行R(Run)和完成 F(Finish)三种状态之一。每个作业的最初状态总是等 待W。 各个等待的作业按照提交时刻的先后次序排队，总是首先调度等待队列中队首的作业。 每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后 要计算并打印这组作业的平均周转时间、带权平均周转时间。调度算法的流程图如下: 思考题： . 编写并调试一个单道处理系统的作业等待模拟程序。 作业等待算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业 的平均周转时间及带权平均周转时间，以比较各种算法的优缺点。 . 编写并调度一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法进行设计。 对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。 . 编写并调试一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于优先级的作业调度。 #include "stdio.h" #include "stdlib.h" #define getjcb(type)(type*)malloc(sizeof(type)) #define NULL 0 struct jcb{char name[10]; int htime; int ntime; char state; struct jcb *link; } *ready=NULL,*p; typedef struct jcb JCB; int input() {int num,i,t=0; void sort(); printf("\n请输入作业个数:"); scanf("%d",&num); for(i=1;i<=num;i++) {printf("\n作业 %d",i); p=(JCB*)malloc(sizeof(JCB)); printf("\n作业名:"); scanf("%s",p->name); printf("\n作业运行时间:"); scanf("%d",&p->ntime); p->htime=t; p->state='w'; p->link=NULL; sort(); t++; }