共查询到20条相似文献,搜索用时 568 毫秒
1.
In this paper, we consider two single-machine rescheduling problems with linear deteriorating jobs under disruption. By a deteriorating jobs, we mean that the actual processing time of the job is an increasing function of its starting time. The two problems correspond to two different increasing linear function. Rescheduling means a set of original jobs has already been scheduled to minimize some classical objective, then a new set of jobs arrives and creates a disruption. We consider the rescheduling problem to minimize the total completion time under a limit of the disruption from the original scheduling. For each problem, we consider two versions. For each version, the polynomial algorithms are proposed, respectively. 相似文献
2.
3.
In many realistic scheduling settings a job processed later consumes more time than when it is processed earlier – this phenomenon is known as scheduling with deteriorating jobs. In the literature on deteriorating job scheduling problems, majority of the research assumed that the actual job processing time of a job is a function of its starting time. In this paper we consider a new deterioration model where the actual job processing time of a job is a function of the processing times of the jobs already processed. We show that the single-machine scheduling problems to minimize the makespan and total completion time remain polynomially solvable under the proposed model. In addition, we prove that the problems to minimize the total weighted completion time, maximum lateness, and maximum tardiness are polynomially solvable under certain agreeable conditions. 相似文献
4.
This paper is to analyze unrelated parallel-machine scheduling resource allocation problems with position-dependent deteriorating jobs. Two general resource consumption functions, the linear and convex resource, are investigated. The objectives are to minimize the cost function that includes the weights of total load, total completion time, total absolute deviation of completion time, and total resource cost. Moreover, we try to minimize the cost function that includes the weights of total load, total waiting time, total absolute deviation of waiting time, and total resource cost. Although each job processing time can be compressed through incurring an additional cost, we show that the problems are polynomial time solvable when the number of machines is fixed. 相似文献
5.
In this paper we consider identical parallel machines scheduling problems with a deteriorating maintenance activity. In this model, each machine has a deteriorating maintenance activity, that is, delaying the maintenance increases the time required to perform it. We need to make a decision on when to schedule the rate-modifying activities and the sequence of jobs to minimize some objective function. We concentrate on two goals separately, namely, minimizing the total absolute differences in completion times (TADC) and the total absolute differences in waiting times (TADW). We show that the problems remain polynomially solvable under the proposed model. 相似文献
6.
研究了具有线性退化及学习效应作用下的单台机器调度问题,对于工件的到达时间是其资源消耗量的正的严格单调递减函数时,考虑了总资源消耗量限定情形下求最大完工时间最小化问题给出了最优算法. 相似文献
7.
In this paper, we consider parallel identical machines scheduling problems with a deteriorating maintenance activity. In this model, each machine has a deteriorating maintenance activity, that is, delaying the maintenance increases the time required to perform it. We need to make a decision on when to schedule the deteriorating maintenance activities and the sequence of jobs to minimize total completion time. We provide a polynomial time algorithm to solve the total completion time minimization problem. 相似文献
8.
《Applied Mathematical Modelling》2014,38(21-22):5231-5238
In this study we consider unrelated parallel machines scheduling problems with learning effect and deteriorating jobs, in which the actual processing time of a job is a function of joint time-dependent deterioration and position-dependent learning. The objective is to determine the jobs assigned to corresponding each machine and the corresponding optimal schedule to minimize a cost function containing total completion (waiting) time, total absolute differences in completion (waiting) times and total machine load. If the number of machines is a given constant, we show that the problems can be solved in polynomial time under the time-dependent deterioration and position-dependent learning model. 相似文献
9.
This paper considers single machine scheduling problems with group technology (GT) and deteriorating jobs. We consider the case of jobs whose processing times are a simple linear function of their starting time. The two objectives of scheduling problems are to minimize the weighted sum of squared completion times and the weighted sum of squared waiting times, respectively. We also provide polynomial time algorithms to solve these problems. 相似文献
10.
J-B Wang 《The Journal of the Operational Research Society》2009,60(4):583-586
The paper deals with the single machine scheduling problems with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the processing time of a job is defined by function of its starting time and total normal processing time of jobs in front of it in the sequence. It is shown that even with the introduction of a time-dependent learning effect and deteriorating jobs to job processing times, the single machine makespan minimization problem remain polynomially solvable. But for the total completion time minimization problem, the classical shortest processing time first rule or largest processing time first rule cannot give an optimal solution. 相似文献
11.
Ji-bo Wang Ai-Xia Guo Feng Shan Bo Jiang Li-Yan Wang 《Journal of Applied Mathematics and Computing》2007,24(1-2):283-293
This paper considers single machine scheduling problems with group technology (GT) and deteriorating jobs. A sequence independent setup is required to process a job from a different group and jobs in each group are processed together. We consider the case of jobs whose processing times are a decreasing function of their starting time. The objectives of scheduling problems are to minimize the makespan and the total completion time, respectively. We also provide polynomial time algorithms to solve these problems. 相似文献
12.
考虑时间和位置相关的单机排序问题, 且机器具有退化的维修限制. 工件的实际加工时间是工件加工位置相关的函数, 目标函数为最大完工时间和总完工时间两个函数, 并利用匹配算法给出这两个问题的多项式时间算法. 最后得出工件满足一定条件时最大完工时间满足组平衡规则. 相似文献
13.
T.C.E. ChengWen-Hsiang Wu Shuenn-Ren ChengChin-Chia Wu 《Applied mathematics and computation》2011,217(21):8804-8824
Scheduling with deteriorating jobs and learning effects has been widely studied. However, multi-agent scheduling with simultaneous considerations of deteriorating jobs and learning effects has hardly been considered until now. In view of this, we consider a two-agent single-machine scheduling problem involving deteriorating jobs and learning effects simultaneously. In the proposed model, given a schedule, we assume that the actual processing time of a job of the first agent is a function of position-based learning while the actual processing time of a job of the second agent is a function of position-based deterioration. The objective is to minimize the total weighted completion time of the jobs of the first agent with the restriction that no tardy job is allowed for the second agent. We develop a branch-and-bound and several simulated annealing algorithms to solve the problem. Computational results show that the proposed algorithms are efficient in producing near-optimal solutions. 相似文献
14.
《高校应用数学学报(英文版)》2020,(2)
The single machine parallel-batch scheduling with deteriorating jobs and rejection is considered in this paper.A job is either rejected,in which a rejection penalty should be paid,or accepted and processed on the machine.Each job's processing time is an increasing linear function of its starting time.The machine can process any number of jobs simultaneously as a batch.The processing time of a batch is equal to the largest processing time of the jobs in the batch.The objectives are to minimize the makespan and the total weighted completion time,respectively,under the condition that the total rejection penalty cannot exceed a given upper bound Q.We show that both problems are NP-complete and present dynamic programming algorithms and fully polynomial time approximation schemes(FPTASs) for the considered problems. 相似文献
15.
This paper considers some scheduling problems with deteriorating jobs. The objectives are to minimize the makespan, the total completion time, the total absolute deviation of completion time, the earliness, tardiness, and due date penalty, the sum of earliness penalties subject to no tardy jobs, respectively. We also explore two resource constrained scheduling problems: how to minimize the resource consumption with makespan constraints and how to minimize the makespan with the total resource consumption constraints. Several polynomial time algorithms are proposed to optimally solve the problems with the above objective functions. 相似文献
16.
Dar-Li YangWen-Hung Kuo 《Applied mathematics and computation》2011,218(5):2069-2073
This paper studies a single machine scheduling problem simultaneously with deteriorating jobs and learning effects. The objectives are to minimize the makespan and the number of tardy jobs, respectively. Two polynomial time algorithms are proposed to solve these problems optimally. 相似文献
17.
Although machine scheduling problems with learning and deteriorating effects consideration have received increasing attention in the recent years, most studies have seldom considered the two phenomena simultaneously. However, learning and deteriorating effects might co-exist in many realistic scheduling situations. Thus, in this article, a model which takes the effects of time-dependent learning and deterioration simultaneously is proposed and applied into some scheduling problems. Under the proposed model, the processing time of a job is determined by a function of its corresponding starting time and positional sequence in each machine. We show that some single machine and flowshop scheduling problems are polynomially solvable with the certain performance measures such as makespan, total completion time, and weighted completion time. 相似文献
18.
Single machine SLK/DIF due window assignment problem with job-dependent linear deterioration effects
We consider single machine scheduling problems with deteriorating jobs and SLK/DIF due window assignment, where the deteriorating rates of jobs are assumed to be job-dependent. We consider two different objectives under SLK and DIF due window assignment, respectively. The first objective is to minimise total costs of earliness, tardiness, due window location and due window size, while the second objective is to minimise a cost function that includes number of early jobs, number of tardy jobs and the costs for due window location and due window size. We study the optimality properties for all problems and develop algorithms for solving these problems in polynomial time. 相似文献
19.
Wen-Chiung Lee 《Optimization Letters》2014,8(1):135-144
Scheduling with learning effect and deteriorating jobs has become more popular. However, most of the research assume that the setup time is negligible or a part of the job processing time. In this paper, we propose a model where the deteriorating jobs, the learning effect, and the setup times are present simultaneously. Under the proposed model, the setup time is past-sequence-dependent and the actual job processing time is a general function of the processing times of the jobs already processed and its scheduled position. We provide the optimal schedules for some single-machine problems. 相似文献
20.
In many realistic scheduling settings a job processed later consumes more time than the same job processed earlier – this is known as scheduling with deteriorating jobs. Most research on scheduling with deteriorating jobs assumes that the actual processing time of a job is an increasing function of its starting time. Thus a job processed late may incur an excessively long processing time. On the other hand, setup times occur in manufacturing situations where jobs are processed in batches whereby each batch incurs a setup time. This paper considers scheduling with deteriorating jobs in which the actual processing time of a job is a function of the logarithm of the total processing time of the jobs processed before it (to avoid the unrealistic situation where the jobs scheduled late will incur excessively long processing times) and the setup times are proportional to the actual processing times of the already scheduled jobs. Under the proposed model, we provide optimal solutions for some single-machine problems. 相似文献