工件加工时间随加工顺序变动的单机排序问题

本文讨论了一类工件加工时间随加工顺序而变的单机排序问题,在目标函数sum from i=1 to nC_i与Lmax下,Smith法则与Jackson法则仍然成立。从而推广了Smith与Jackson的结果。一般所考虑的单机排序问题是:有n个工件需要在一台机器上加工,而该机器只能一次加工一个工件,且工件j在该机器上所需的加工时间为P_i,这里P_j为一常量,即与工件早加工或晚加工无关。现在需要确定工件加工的一个顺序,使得在不同的目标下最优。     

单机排序中一个极小最大绝对迟后问题

本文考虑n个工件在单机上加工的排序问题,工作j的预期开始加工时间和所需加工时间分别为αj,pj,应交工时间为dj=αj kpj d,这里的k(≥0),d是待定的变量,目标函数为极小化最大绝对迟后。本文首先考虑了该问题一些特殊情况的研究结果,然后在强一致性条件下证得此问题O(nlogn)可解。     

带调整时间的一类排序问题

进一步讨论带磨损因子的排序问题,在相应问题中对工件j,j=1,2,…,n,引入了调整时间sj,它同磨损因子bj一样同该工件何时加工无关.要求适当排列这n个工件的加工顺序,使目标函数值达最小.给出了加工全程、完工时间之和及JIT问题在引入调整时间下的最优算法.     

三机流水作业问题若干特殊情形的NP困难性

本文研究以加工总为目标函数的三台机器流水作业问题的特殊情形的计算复杂性,证明了下列情形为ＮＰ困难的：所有工作在第二台机器上有相同的加工时间;所有工作在第一和第三台机器上有相册的加工时间;每个工件至少有一个零工序;每个工件有一个丢失的工序。     

具有时间与位置相关及维修限制的单机排序问题

考虑时间和位置相关的单机排序问题, 且机器具有退化的维修限制. 工件的实际加工时间是工件加工位置相关的函数, 目标函数为最大完工时间和总完工时间两个函数, 并利用匹配算法给出这两个问题的多项式时间算法. 最后得出工件满足一定条件时最大完工时间满足组平衡规则.     

基于重新排序的退化工件最小化总延误时间问题

考虑了错位限制下的含有退化工件的重新排序问题,即工件的实际加工时间看作是工件开工时间的线性函数．重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有一新工件集到达,新工件的安排使得原始工件重新排序进而产生错位．研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题,其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率αj非减的序列排列,基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法．     

平行机中关于关于同类机近似算法的研究

我们考虑平行机排序问题中的这样一类:机器两台,类型一样,但效率不同.其中n个工件在第一台机器上的加工时间分别为p1,p2,…,Pn,在第二台机器上的加工时间分别为αρ1,αρ2,…,αρn,其中0<α≤1.每台机器上的工件总数不受限制.n个工件的权分别为w1,w2,…,wn,我们的目标是如何在这两台机器上安排这n个工件以及如何确定每台机器上工件加工的先后顺序,使得这n个工件的完工时间的总权和 达到最小.该问题记为 .对于这个问题,我们给出一个1.1755近似算法.     

单处理机在加工时间相同准备时间可控时的∑w_jC_j问题

一组n个工件需在一台机器上加工,工件j所需的准备时间、加工时间分别为rj,pj,可压缩准备时间为x_j,0≤x_j≤r_j,其中rj,pj,xj均为非负整数。由同压缩向量x有关的某一目标函数F_1和压缩费用F_2=∑xj可构成文中的四个多目标排序问题(P1)-(P4),这种可控准备时间的多目标排序问题由引文[2]的作者在1990年提出并作     

单机最优交货期决策及工件排序

本文考虑n个独立工件在一台机器上加工的排序问题,每个工件J_i的交货期设置为d_i=kP_i~α(α≥1),目标是寻找工件最优加工时间乘子及工件最优排序S(?),使工件完工时间与交货期的最大偏差最小。给出寻找最优加工时间乘子k(?)及工件最优排序S(?)的方法。     

无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案

本文考虑n个工件的无限批量机器调度问题．一台机器可以同时加工B≥n个工件．每个工件具有一个正权因子、一个释放时间和一个加工时间．一个批次的加工时间是该批次所包含所有工件的加工时间的最大者．在同一批次中加工的工件有相同的完工时间，即它们的共同开始时间加上该批次的加工时间．对于最小化加权完工时间和问题，本文给出了第一个多项式时间近似方案(PTAS)．对任意给定精度，该算法的运行时间为线性的．     

Single-machine scheduling with effects of exponential learning and general deterioration

The purpose of this study is to explore the single-machine scheduling with the effects of exponential learning and general deterioration. By the effects of exponential learning and general deterioration, we meant that job processing time is decided by the functions of their starting time and positions in the sequence. Results showed that with the introduction of learning effect and deteriorating jobs to job processing time, single-machine makespan, and sum of completion time (square) minimization problems remained polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion time and the maximum lateness, this paper proved that the weighted smallest basic processing time first (WSPT) rule and the earliest due date first (EDD) rule constructed the optimal sequence under some special cases, respectively.     

Trapezoidal type inequalities for n-time differentiable functions

In this paper we consider the flow shop scheduling problems with the effects of learning and deterioration. In this model the processing times of a job is defined as a function of its starting time and position in a sequence. The scheduling objective functions are makespan and total completion time. We prove that even with the introduction of learning effect and deteriorating jobs to job processing times, some special flow shop scheduling problems remain polynomially solvable.     

Optimal due-date assignment problem with learning effect and resource-dependent processing times

In this paper, we consider a single-machine earliness-tardiness scheduling problem with due-date assignment, in which the processing time of a job is a function of its position in a sequence and its resource allocation. The due date assignment methods studied include the common due date, and the slack due date, which reflects equal waiting time allowance for the jobs. For each combination of due date assignment method and processing time function, we provide a polynomial-time algorithm to find the optimal job sequence, due date values, and resource allocations that minimize an integrated objective function, which includes earliness, tardiness, due date assignment, and total resource consumption costs.     

带强制工期的可中断单机排序问题

工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.本文讨论了在单机上,加工带准备时间与强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过奇偶划分问题归约,证明了其是NP-complete的.而后,讨论了加工时间相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序,因此提出了—个多项式时间算法,既能判定可行性,又能针对可行问题获得最优排序.     

Some single-machine scheduling with both learning and deterioration effects

In this paper we consider the single-machine scheduling problems with both learning and deterioration effects. By the effects of learning and deterioration, we mean that job processing times are defined by functions of their starting times and positions in the sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, single-machine makespan minimization problem and the sum of the θth power of job completion times minimization problem remain polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion times and the maximum lateness, this paper proves that the WSPT rule and the EDD rule can construct the optimal sequence under some special cases, respectively.     

Learning effect and deteriorating jobs in the single machine scheduling problems

This paper studies the single machine scheduling problems with learning effect and deteriorating jobs simultaneously. In this model, the processing times of jobs are defined as functions of their starting times and positions in a sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, the makespan, the total completion time and the sum of the k$k$th power of completion times minimization problems remain polynomially solvable, respectively. But for the following objective functions: the total weighted completion time and the maximum lateness, this paper proves that the shortest weighted processing time first (WSPT) rule and the earliest due-date first (EDD) rule can construct the optimal sequence under some special cases, respectively.     

Single machine scheduling with exponential learning functions

In this paper we consider the single machine scheduling problem with exponential learning functions. By the exponential learning functions, we mean that the actual job processing time is a function of the total normal processing times of the jobs already processed. We prove that the shortest processing time (SPT) rule is optimal for the total lateness minimization problem. For the following three objective functions, the total weighted completion time, the discounted total weighted completion time, the maximum lateness, we present heuristic algorithms according to the corresponding problems without exponential learning functions. We also analyse the worst-case bound of our heuristic algorithms. It also shows that the problems of minimizing the total tardiness and discounted total weighted completion time are polynomially solvable under some agreeable conditions on the problem parameters.