Single-machine scheduling with nonlinear deterioration

In this paper, we consider the single-machine scheduling problems with nonlinear deterioration. By the nonlinear deterioration effect, we mean that the processing times of jobs are nonlinear functions of their starting times. We show that even with the introduction of nonlinear deterioration to job processing times, single machine makespan minimization problem remains polynomially solvable. We also show that an optimal schedule of the total completion time minimization problem is V-shaped with respect to job normal processing times. A heuristic algorithm utilizing the V-shaped property is proposed, and computational experiments show that it performs effectively and efficiently in obtaining near-optimal solutions.     

需要安装时间的平行多功能机排序问题的启发式算法

考虑需要安装时间的平行多功能机排序问题。在该模型中,每个工件对应机器集合的一个子集,其只能在这个子集中的任一台机器上加工,称这个子集为该工件的加工集合;工件分组,同组工件具有相同的加工时间和加工集合,不同组中的工件在同一台机器上连续加工需要安装时间,目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法:首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能,大量的计算实验表明,算法是实用而有效的。     

Single-machine total completion time scheduling with a time-dependent deterioration

In this paper, we consider the single-machine scheduling problems with a time-dependent deterioration. By the time-dependent deterioration, we mean that the processing time of a job is defined by an increasing function of total normal processing time of jobs in front of it in the sequence. The objective is to minimize the total completion time. We develop a mixed integer programming formulation for the problem. The complexity status of this problem remains open. Hence, we use the smallest normal processing time (SPT) first rule as a heuristic algorithm for the general cases and analyze its worst-case error bound. Two heuristic algorithms utilize the V-shaped property are also proposed to solve the problem. Computational results are presented to evaluate the performance of the proposed algorithms.     

A Heuristic Solution Procedure to Minimize Makespan on a Single Machine with Non-linear Cost Functions

We consider the static single-facility scheduling problem where the processing times of jobs are a nondecreasing and differentiable function of their starting (waiting) times and the objective is to minimize the total elapsed time (makespan) in which all jobs complete their processing. We give a criterion for optimality of two jobs to be scheduled next to each other, and based on this criterion we propose a heuristic algorithm to solve the problem. The effectiveness of the algorithm is empirically evaluated for quadratic and exponential cost functions. In the quadratic case it is compared with the static heuristic algorithm proposed by Gupta and Gupta.     

Single facility scheduling with multiple job classes

This paper considers a static single facility scheduling problem where jobs are divided into several mutually exclusive classes. The jobs in a given class need not be processed together. In addition to a known processing time for each job, there is a switching time involved which depends on the class of the job immediately preceding a job. A heuristic algorithm is proposed to find a minimum mean flow time schedule. The effectiveness of the proposed heuristic algorithm is empirically evaluated and found to indicate that the solutions obtained from this heuristic algorithm are often close to optimal.     

A heuristic for scheduling in a two-stage hybrid flowshop with renewable resources shared among the stages

In this paper we propose a heuristic for solving the problem of resource constrained preemptive scheduling in the two-stage flowshop with one machine at the first stage and parallel unrelated machines at the second stage, where renewable resources are shared among the stages, so some quantities of the same resource can be used at different stages at the same time. Availability of every resource at any moment is limited and resource requirements of jobs are arbitrary. The objective is minimization of makespan. The problem is NP-hard. The heuristic first sequences jobs on the machine at stage 1 and then solves the preemptive scheduling problem at stage 2. Priority rules which depend on processing times and resource requirements of jobs are proposed for sequencing jobs at stage 1. A column generation algorithm which involves linear programming, a tabu search algorithm and a greedy procedure is proposed to minimize the makespan at stage 2. A lower bound on the optimal makespan in which sharing of the resources between the stages is taken into account is also derived. The performance of the heuristic evaluated experimentally by comparing the solutions to the lower bound is satisfactory.     

Single-machine scheduling to minimize total absolute differences in waiting times with deteriorating jobs

In this paper we consider a single-machine scheduling problem with simple linear deterioration. By simple linear deterioration, we mean that the processing time of a job is a simple linear function of its execution starting time and its deterioration rate. The objective is to find a schedule that minimizes total absolute differences in waiting times. We show that the optimal schedule is V-shaped: jobs are arranged in descending order of their deterioration rates if they are placed before the job with the smallest deterioration rate, but in ascending order of their deterioration rates if placed after it. We prove other several properties of an optimal schedule, and introduce two efficient heuristic algorithms that are tested against a lower bound. We also provide computational results to evaluate the performance of the heuristic algorithms.     

Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration

In this paper, we address a two-machine flow shop scheduling problem under simple linear deterioration. By a simple linear deterioration function, we mean that the processing time of a job is a simple linear function of its execution start time. The objective is to find a sequence that minimizes total weighted completion time. Optimal schedules are obtained for some special cases. For the general case, several dominance properties and two lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational analysis on randomly generated problems is conducted to evaluate the branch-and-bound algorithm and heuristic algorithm.     

Scheduling linear deteriorating jobs to minimize the number of tardy jobs

In this paper a problem of scheduling a single machine under linear deterioration which aims at minimizing the number of tardy jobs is considered. According to our assumption, processing time of each job is dependent on its starting time based on a linear function where all the jobs have the same deterioration rate. It is proved that the problem is NP-hard; hence a branch and bound procedure and a heuristic algorithm with O(n ²) is proposed where the heuristic one is utilized for obtaining the upper bound of the B&B procedure. Computational results for 1,800 sample problems demonstrate that the B&B method can solve problems with 28 jobs quickly and in some other groups larger problems are also solved. Generally, B&B method can optimally solve 85% of the samples which shows high performance of the proposed method. Also it is shown that the average value of the ratio of optimal solution to the heuristic algorithm result with the objective ??(1 ? Ui) is at most 1.11 which is more efficient in comparison to other proposed algorithms in related studies in the literature.     

带准备时间的单机指数时间学习效应排序问题

研究带有准备时间的单机学习效应模型,其中工件加工时间具有指数时间学习效应,即工件的实际加工时间是已经排好的工件加工时间的指数函数。学习效应模型考虑工件的实际加工时间同时依赖于工件本身的加工时间和已加工工件的累计加工时间,目标函数为最小化总完工时间。这个问题是NP-难的,提出了一个数学规划模型来求解该问题的最优解。通过分析几个优势性质和下界,提出分支定界算法来求解此问题,并设计启发式算法改进分支定界算法的上界值。通过仿真实验验证了分支定界算法在求解质量和时间方面的有效性。     

Minimizing total completion time on a single machine with step improving jobs

Production systems often experience a shock or a technological change, resulting in performance improvement. In such settings, job processing times become shorter if jobs start processing at, or after, a common critical date. This paper considers a single machine scheduling problem with step-improving processing times, where the effects are job-dependent. The objective is to minimize the total completion time. We show that the problem is NP-hard in general and discuss several special cases which can be solved in polynomial time. We formulate a Mixed Integer Programming model and develop an LP-based heuristic for the general problem. Finally, computational experiments show that the proposed heuristic yields very effective and efficient solutions.     

A single-machine scheduling problem with two-agent and deteriorating jobs

Deteriorating jobs scheduling problems have been extensively studied in recent years. However, it is assumed that there is a common goal to minimize for all jobs in most of the research. In many management situations, multiple agents compete on the usage of a common processing resource. In this paper, we considered a single-machine scheduling problem with a linear deterioration assumption where the objective is to minimize the total weighted completion time of jobs from the first agent with the restriction that no tardy job is allowed for the second agent. We proposed a branch-and-bound algorithm and three heuristic algorithms to search for the optimal solution and near-optimal solutions, respectively. A computational experiment was conducted to evaluate the performance of the proposed algorithms.     

Scheduling jobs with truncated exponential learning functions

In this paper we consider the single machine scheduling problem with truncated exponential learning functions. By the truncated exponential learning functions, we mean that the actual job processing time is a function which depends not only on the total normal processing times of the jobs already processed but also on a control parameter. The use of the truncated function is to model the phenomenon that the learning of a human activity is limited. We show that even with the introduction of the proposed model to job processing times, several single machine problems remain polynomially solvable. 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 truncated exponential learning functions. We also analyse the worst-case bound of our heuristic algorithms.     

Two-agent scheduling with position-based deteriorating jobs and learning effects

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.     

Minimizing flow time in a flow-line manufacturing cell with family setup times

This paper considers the problem of scheduling part families and jobs within each part family in a flowline manufacturing cell with independent family setup times where parts (jobs) in each family are processed together. The objective is to minimize total flow time. A branch-and-bound algorithm capable of solving moderate sized problems is developed. Several heuristic algorithms are proposed and empirically evaluated as to their effectiveness and efficiency in finding optimal permutation schedules. These results show that several heuristic algorithms generate solutions that are better than those generated by an existing genetic algorithm.     

具有恶化效应和凸资源分配关系的单机排序问题

研究工件加工时间具有恶化效应和凸资源关系的单机排序问题,其中工件的实际加工时间是其正常的加工时间,工件开工时间(具有恶化效应)及消耗资源量的函数。目标为在最大完工时间(总完工时间、总等待时间、完工时间总绝对差与等待时间总绝对差)小于或等于给定常数的条件下找到工件的最优排序和最优的资源分配使工件的总资源消耗量最少。在单机状态下,证明了此问题是多项式时间可解的,并给出了求解该问题的算法和数值实例。     

Single-machine scheduling with logarithm deterioration

Traditionally, job processing times are assumed to be known and fixed; however, there are many situations in which a job that is processed later consumes more time than the same job when it is processed earlier. This is known as deteriorating jobs scheduling in the literature. Most of the research in deteriorating jobs scheduling assumes that the actual job processing time is a linear function of its starting time. Thus, the actual job processing times might increase significantly if the number of jobs or the job sizes increase. Motivated by this limitation, this paper addresses a new deterioration model where the actual job processing time is a function of the logarithm of the job processing times already processed. Under the proposed model, we provide the optimal solutions for some single-machine problems.     

A bicriteria parallel machine scheduling with a learning effect of setup and removal times

In studies on scheduling problems, generally setup times and removal times of jobs have been neglected or by including those into processing times. However, in some production systems, setup times and removal times are very important such that they should be considered independent from processing times. Since, in general jobs are done according to automatic machine processes in production systems processing times do not differ according to process sequence. But, since human factor becomes influential when setup times and removal times are taken into consideration, setup times will be decreasing by repeating setup processes frequently. This fact is defined with learning effect in scheduling literature. In this study, a bicriteria m-identical parallel machines scheduling problem with a learning effect of setup times and removal times is considered. The objective function of the problem is minimization of the weighted sum of total completion time and total tardiness. A mathematical programming model is developed for the problem which belongs to NP-hard class. Results of computational tests show that the proposed model is effective in solving problems with up to 15 jobs and five machines. We also proposed three heuristic approaches for solving large jobs problems. According to the best of our knowledge, no work exists on the minimization of the weighted sum of total completion time and total tardiness with a learning effect of setup times and removal times.     

Two-machine flowshop scheduling problems involving a batching machine with transportation or deterioration consideration

This paper considers two scheduling problems for a two-machine flowshop where a single machine is followed by a batching machine. The first problem is that there is a transporter to carry the jobs between machines. The second problem is that there are deteriorating jobs to be processed on the single machine. For the first problem with minimizing the makespan, we formulate it as a mixed integer programming model and then prove that it is strongly NP-hard. A heuristic algorithm is proposed for solving this problem and its worst case performance is analyzed. The computational experiments are carried out and the numerical results show that the heuristic algorithm is effective. For the second problem, we derive the optimal algorithms with polynomial time for minimizing the makespan, the total completion time and the maximum lateness, respectively.     

Minimizing Completion Time Variance with Compressible Processing Times

We introduce a new formulation of the standard completion time variance (CTV) problem with n jobs and one machine, in which the job sequence and the processing times of the jobs are all decision variables. The processing time of job i (i=1, ,n) can be compressed by an amount within [l_i, u_i], which however will incur a compression cost. The compression cost is a general convex non-decreasing function of the amount of the job processing time compressed. The objective is to minimize a weighted combination of the completion time variance and the total compression cost. We show that, under an agreeable condition on the bounds of the processing time compressions, a pseudo-polynomial algorithm can be derived to find an optimal solution for the problem. Based on the pseudo-polynomial time algorithm, two heuristic algorithms H1 and H2 are proposed for the general problem. The relative errors of both heuristic algorithms are guaranteed to be no more than , where is a measure of deviation from the agreeable condition. While H1 can find an optimal solution for the agreeable problem, H2 is dominant for solving the general problem. We also derive a tight lower bound for the optimal solution of the general problem. The performance of H2 is evaluated by complete enumeration for small n, and by comparison with this tight lower bound for large n. Computational results (with n up to 80) are reported, which show that the heuristic algorithm H2 in general can efficiently yield near optimal solutions, when n is large.