Single-machine ready times scheduling with group technology and proportional linear deterioration

Scheduling research has increasingly taken the concept of deterioration into consideration. In this paper, we study a single machine group scheduling problem with deterioration effect, where the jobs are already put into groups, before any optimization. We assume that the actual processing times of jobs are increasing functions of their starting times, i.e., the job processing times are described by a function which is proportional to a linear function of time. The setup times of groups are assumed to be fixed and known. For some special cases of minimizing the makespan with ready times of the jobs, we show that the problem can be solved in polynomial time for the proposed model. For the general case, a heuristic algorithm is proposed, and the computational experiments show that the performance of the heuristic is fairly accurately in obtaining near-optimal solutions. The results imply that the average percentage error of the proposed heuristic algorithm from optimal solutions is less than 3%.     

Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem

We study a static stochastic single machine scheduling problem in which jobs have random processing times with arbitrary distributions, due dates are known with certainty, and fixed individual penalties (or weights) are imposed on both early and tardy jobs. The objective is to find an optimal sequence that minimizes the expected total weighted number of early and tardy jobs. The general problem is NP-hard to solve; however, in this paper, we develop certain conditions under which the problem is solvable exactly. An efficient heuristic is also introduced to find a candidate for the optimal sequence of the general problem. Our illustrative examples and computational results demonstrate that the heuristic performs well in identifying either optimal sequences or good candidates with low errors. Furthermore, we show that special cases of the problem studied here reduce to some classical stochastic single machine scheduling problems including the problem of minimizing the expected weighted number of early jobs and the problem of minimizing the expected weighted number of tardy jobs which are both solvable by the proposed exact or heuristic methods.     

加工时间和尺寸成正比单机排序和工件运输的最小化最大完工时间问题

在单机排序和工件运输的最小化最大完工时间问题中,工件首先在一台机器上加工,然后被一辆有容量限制的汽车运送到一个顾客．当工件的加工时间和尺寸无关时, Chang和Lee已经证明该问题是强NP困难的．他们也给出了一个启发式算法,它的最差执行比为5／3,并且这个界是紧的．本文考虑工件的加工时间和尺寸成正比的情形,证明了Chang和Lee的算法有更好的最差执行比53／35,并提供了一个新的启发式算法,它的最差执行比是3／2,并且这个界是最好的．     

Numerical Methods for Single Machine Scheduling with Non-linear Cost Functions to Minimize Total Cost

In this paper we are concerned with the problem of sequencing a given set of jobs without preemption on a single machine so as to minimize total cost, where associated with each job is a processing time and a differentiable cost function defined on the completion time of the job. The problem, in general, is NP-complete and, therefore, there is unlikely to be an algorithm to solve the problem in reasonable time, thus a heuristic algorithm is desirable. We present two heuristic algorithms to solve the problem. The first algorithm is based on the differential of the cost functions, and the second algorithm is based on the least square approximation of the cost functions. Computational experiences for the case of quadratic, cubic, and exponential cost functions are presented.     

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.     

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

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

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-难的一般情况设计启发式算法:首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能,大量的计算实验表明,算法是实用而有效的。     

Two-machine flow shop total tardiness scheduling problem with deteriorating jobs

This paper studies a two-machine scheduling problem with deteriorating jobs which their processing times depend on their waiting time. We develop a branch and bound algorithm to minimize the total tardiness criteria. A lower bound, several dominance properties and an initial upper bound derived from a heuristic algorithm are used to increase the speed of branch and bound algorithm and decrease its required memory space. Computational results are presented to evaluate effectiveness and efficiency of the algorithms.     

Scheduling coupled-operation jobs with exact time-lags

Scheduling coupled-operation jobs with exact time-lags on a single machine has a wide range of applications. In that problem, each job consists of two operations with given processing times, which should be scheduled on a single machine observing a given time-lag. The general case of the problem with arbitrary processing times of operations and arbitrary time lags is known to be NP-hard in the strong sense and the problem remains NP-hard for many special cases. In order to develop a local search algorithm for the problem, we first explore two possible approaches for representing feasible solutions and their neighborhoods based on maintaining a permutation of first operations of the jobs or maintaining a full permutation of all operations. The first representation appears to be unpromising since, as we prove, the problem of finding an optimal sequence of second operations for a fixed sequence of first operations is NP-hard in the strong sense even in the case of unit processing times. We elaborate the second approach by developing a tabu search heuristic based on efficient job re-insertion. Empirical evaluation demonstrates superiority of the developed algorithm in comparison with the earlier published algorithms.     

A variable neighbourhood search for hybrid flow-shop scheduling problem with rework and set-up times

This paper deals with hybrid flow-shop scheduling problem with rework. In this problem, jobs are inspected at the last stage, and poorly processed jobs were returned and processed again. Thus, a job may visit a stage more than once, and we have a hybrid flow-shop with re-entrant flow. This kind of a shop may occur in many industries, such as final inspection system in automotive manufacturing. The criterion is to minimize the makespan of the system. We developed a 0–1 mixed-integer program of the problem. Since the hybrid flow-shop scheduling problem is NP-hard, an algorithm for finding an optimal solution in polynomial time does not exist. So we generalized some heuristic methods based on several basic dispatching rules and proposed a variable neighbourhood search (VNS) for the problem with sequence-dependent set-up times and unrelated parallel machines. The computational experiments show that VNS provides better solutions than heuristic methods.     

Resource constraint scheduling with a fractional shared resource

We consider a scheduling problem motivated by mining in remote off-grid areas. In this model, mines have pre-assigned mineral processing jobs and their own machine for executing these jobs. Each job also needs a certain amount of electricity in order to get completed. The electricity, on the other hand, is of limited supply and must be shared between the mines. We present a mathematical formulation of the problem and a Lagrangian relaxation based heuristic. Computational results which compares our heuristic with genetic algorithm and simulated annealing are also presented.     

Scheduling of a Two-machine Flowshop with Processing Time Linearly Dependent on Job Waiting-time

This paper deals with the problem of finding the minimum finish-time schedule in a two-machine flowshop, where the processing times of jobs are linearly dependent on the job waiting-times. The problem is shown to be NP-hard. A heuristic algorithm is presented, and the worst-case bounds are derived for the different variations of the algorithm.     

A scheduling problem with job values given as a power function of their completion times

This paper deals with a problem of scheduling jobs on the identical parallel machines, where job values are given as a power function of the job completion times. Minimization of the total loss of job values is considered as a criterion. We establish the computational complexity of the problem – strong NP-hardness of its general version and NP-hardness of its single machine case. Moreover, we solve some special cases of the problem in polynomial time. Finally, we construct and experimentally test branch and bound algorithm (along with some elimination properties improving its efficiency) and several heuristic algorithms for the general case of the problem.     

Two-machine open shop scheduling with special transportation times

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimise the makespan, provided that preemption is not allowed and the interstage transportation times are involved. In general, this problem is known to be NP-hard. We present a linear time algorithm that finds an optimal schedule if no transportation time exceeds the smallest of the processing times. We also describe an algorithm that creates a heuristic solution to the problem with job-independent transportation times. Our algorithm provides a worst-case performance ratio of 8/5 if the transportation time of a job depends on the assigned processing route. The ratio reduces to 3/2 if all transportation times are equal.     

An algorithm for single machine sequencing with deadlines to minimize total weighted completion time

Each of n jobs is to be processed without interruption on a single machine. Each job becomes available for processing at time zero, has a deadline by which it must be completed and has a positive weight. The objective is to find a processing order of the jobs which minimizes the sum of weighted completion times. In this paper a branch and bound algorithm for the problem is presented which incorporates lower bounds that are obtained using a new technique called the multiplier adjustment method. Firstly several dominance conditions are derived. Then a heuristic is described and sufficient conditions for its optimality are given. The lower bound is obtained by performing a Lagrangean relaxation of the deadline constraints; the Lagrange multipliers are chosen so that the sequence generated by the heuristic is an optimal solution of the relaxed problem, thus yielding a lower bound. The algorithm is tested on problems with up to fifty jobs.     

Minimizing makespan on a single burn-in oven in semiconductor manufacturing

This paper considers a scheduling problem for a single burn-in oven in semiconductor manufacturing industry where the oven is a batch processing machine and each batch processing time is represented by the largest processing time among those of all the jobs contained in the batch. The objective measure of the problem is the maximum completion time (makespan) of all jobs. This paper investigates a static case in which all jobs are available to process at time zero, and also analyzes a dynamic case with different job-release times, for which a branch-and-bound algorithm and several heuristics are exploited. The worst case error performance ratios of the heuristics are also derived.     

An algorithm for single machine sequencing with release dates to minimize total weighted completion time

Each of n jobs is to be processed without interruption on a single machine which can handle only one job at a time. Each job becomes available for processing at its release date, requires a processing time and has a positive weight. Given a processing order of the jobs, the earliest completion time for each job can be computed. The objective is to find a processing order of the jobs which minimizes the sum of weighted completion times. In this paper a branch and bound algorithm for the problem is derived. Firstly a heuristic is presented which is used in calculating the lower bound. Then the lower bound is obtained by performing a Lagrangean relaxation of the release date constraints; the Lagrange multipliers are chosen so that the sequence generated by the heuristic is an optimum solution of the relaxed problem thus yielding a lower bound. A method to increase the lower bound by deriving improved constraints to replace the original release date constraints is given. The algorithm, which includes several dominance rules, is tested on problems with up to fifty jobs. The computational results indicate that the version of the lower bound using improved constraints is superior to the original version.     

Scheduling interfering job sets on parallel machines

We consider bicriteria scheduling on identical parallel machines in a nontraditional context: jobs belong to two disjoint sets, and each set has a different criterion to be minimized. The jobs are all available at time zero and have to be scheduled (non-preemptively) on m parallel machines. The goal is to generate the set of all non-dominated solutions, so the decision maker can evaluate the tradeoffs and choose the schedule to be implemented. We consider the case where, for one of the two sets, the criterion to be minimized is makespan while for the other the total completion time needs to be minimized. Given that the problem is NP-hard, we propose an iterative SPT–LPT–SPT heuristic and a bicriteria genetic algorithm for the problem. Both approaches are designed to exploit the problem structure and generate a set of non-dominated solutions. In the genetic algorithm we use a special encoding scheme and also a unique strategy – based on the properties of a non-dominated solution – to ensure that all parts of the non-dominated front are explored. The heuristic and the genetic algorithm are compared with a time-indexed integer programming formulation for small and large instances. Results indicate that the both the heuristic and the genetic algorithm provide high solution quality and are computationally efficient. The heuristics proposed also have the potential to be generalized for the problem of interfering job sets involving other bicriteria pairs.     

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.