CAJ | 학술논문

针对两台同构并行机上的在线批调度问题，提出了使工件加工的最大完成时间最小的一个批在线列表调度算法。即工件组成不同的批，每个批中有m个工件，当每批到达等待加工时，其内部的工件加工时间才已知，且每个工件加工时间限定在某个实区间[ a，b]上。在对当前批后批中工件的信息不了解的情况下，立即将其中的工件按LPT规则调度进行调度，调度过程中不允许中断。解决了算法的可使用性的度量问题，对其最坏情况进行了分析，给出了算法的最坏情况比。
침대량태동구병행궤상적재선비조도문제，제출료사공건가공적최대완성시간최소적일개비재선렬표조도산법。즉공건조성불동적비，매개비중유m개공건，당매비도체등대가공시，기내부적공건가공시간재이지，차매개공건가공시간한정재모개실구간[ a，b]상。재대당전비후비중공건적신식불료해적정황하，립즉장기중적공건안LPT규칙조도진행조도，조도과정중불윤허중단。해결료산법적가사용성적도량문제，대기최배정황진행료분석，급출료산법적최배정황비。
An algorithm was put forward to satisfy the batch on-line scheduling on two identical parallel machines with the objective to minimize the maximum completion time. In the algorithm,all workpieces were divided into different batches,and each batch has m workpieces. The processing times of workpieces in every batch were given only when the batch containing them arrived and they were constrained in some interval[ a,b]. When a batch arrived,the work-pieces in this batch were scheduled immediately and irrevocably with the unknown following batches. An algorithm with scheduling workpieces in every batch by LPT rule was proposed. The measurement of the algorithm application was solved,the worst case was analyzed and the worst case ratio was given.