Single machine total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs

In this article, we consider a single machine scheduling problem with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the job processing time is defined by a function of its starting time and total normal processing time of jobs in front of it in the sequence. The objective is to determine an optimal schedule so as to minimize the total completion time. This problem remains open for the case of ?1?a?a denotes the learning index; we show that an optimal schedule of the problem is V-shaped with respect to job normal processing times. Three heuristic algorithms utilising the V-shaped property are proposed, and computational experiments show that the last heuristic algorithm performs effectively and efficiently in obtaining near-optimal solutions.     

Two-machine flow shop problem with effects of deterioration and learning

In this paper we consider a two-machine flow shop scheduling problem with effects of deterioration and learning. By the effects of deterioration and learning, we mean that the processing time of a job is a function of its execution starting time and its position in a sequence. The objective is to find a sequence that minimizes the total completion time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and some lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed, which is shown by computational experiments to perform effectively and efficiently in obtaining near-optimal solutions.     

A new heuristic for scheduling the two-stage flowshop with additional resources

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines at the first stage and a single machine at the second stage. At the first stage, jobs use some additional resources which are available in limited quantities at any time. The resource requirements are of 0–1 type. The objective is the minimization of makespan. The problem is NP-hard. Heuristic algorithms are proposed which solve to optimality the resource constrained scheduling problem at the first stage of the flowshop, and at the same time, minimize the makespan in the flowshop by selecting appropriate jobs for simultaneous processing. Several rules of job selection are considered. The performance of the proposed heuristic algorithms is analyzed by comparing solutions with the lower bound on the optimal makespan. The extensive computational experiment shows that the proposed heuristic algorithms are able to produce near-optimal solutions in short computational time.     

Single-machine makespan minimization scheduling with nonlinear shortening processing times

In this paper, we consider the single-machine makespan minimization scheduling problem with nonlinear shortening processing times. By the nonlinear shortening processing times, we mean that the processing times of jobs are non-increasing nonlinear functions of their starting times. The computational complexity of the general problem remains an open problem, but we show that even with the introduction of nonlinear shortening processing times to job processing times, some special cases remain polynomially solvable. We also show that an optimal schedule of the general makespan minimization problem is V-shaped with respect to job normal processing times. A heuristic algorithm which utilize the V-shaped property is proposed, and computational experiments show that it is effective and efficient in obtaining near-optimal solutions.     

Two-machine flow shop scheduling with linear decreasing job deterioration

In this paper, we consider a two-machine flow shop scheduling problem with deteriorating jobs. By a deteriorating job, we mean that the processing time is a decreasing function of its execution start time. A proportional linear decreasing deterioration function is assumed. The objective is to find a sequence that minimizes total completion time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and some 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 results for randomly generated problem instances are presented, which show that the heuristic algorithm effectively and efficiently in obtaining near-optimal solutions.     

A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem

In this paper, we study the job shop scheduling problem with the objective of minimizing the total weighted tardiness. We propose a hybrid shifting bottleneck-tabu search (SB-TS) algorithm by replacing the re-optimization step in the shifting bottleneck (SB) algorithm by a tabu search (TS). In terms of the shifting bottleneck heuristic, the proposed tabu search optimizes the total weighted tardiness for partial schedules in which some machines are currently assumed to have infinite capacity. In the context of tabu search, the shifting bottleneck heuristic features a long-term memory which helps to diversify the local search. We exploit this synergy to develop a state-of-the-art algorithm for the job shop total weighted tardiness problem (JS-TWT). The computational effectiveness of the algorithm is demonstrated on standard benchmark instances from the literature.     

A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates

This paper presents a bicriterion analysis of time/cost trade-offs for the single-machine scheduling problem where both job processing times and release dates are controllable by the allocation of a continuously nonrenewable resource. Using the bicriterion approach, we distinguish between our sequencing criterion, namely the makespan, and the cost criterion, the total resource consumed, in order to construct an efficient time/cost frontier. Although the computational complexity of the problem of constructing this frontier remains an open question, we show that the optimal job sequence is independent of the total resource being used; thereby we were able to reduce the problem to a sequencing one. We suggest an exact dynamic programming algorithm for solving small to medium sizes of the problem, while for large-scale problems we present some heuristic algorithms that turned out to be very efficient. Five different special cases that are solvable by using polynomial time algorithms are also presented.     

Minimizing total weighted flowtime subject to minimum makespan on two identical parallel machines

We study the problem of scheduling n jobs on two identical parallel processors or machines where an optimal schedule is defined as one with the shortest total weighted flowtime (i.e., the sum of the weighted completion time of all jobs), among the set of schedules with minimum makespan (i.e., the completion time of the last job finished). We present a two phase non-linear Integer Programming formulation for its solution, admittedly not to be practical or useful in most cases, but theoretically interesting since it models the problem. Thus, as an alternative, we propose an optimization algorithm, for small problems, and a heuristic, for large problems, to find optimal or near optimal solutions. Furthermore, we perform a computational study to evaluate and compare the effectiveness of the two proposed methods.     

Permutation flowshop problems with bi-criterion makespan and total completion time objective and position-weighted learning effects

In this paper, we study the problem of minimizing the weighted sum of makespan and total completion time in a permutation flowshop where the processing times are supposed to vary according to learning effects. The processing time of a job is a function of the sum of the logarithms of the processing times of the jobs already processed and its position in the sequence. We present heuristic algorithms, which are modified from the optimal schedules for the corresponding single machine scheduling problem and analyze their worst-case error bound. We also adopt an existing algorithm as well as a branch-and-bound algorithm for the general m-machine permutation flowshop problem. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems.     

A heuristic algorithm to minimize total weighted tardiness on a single machine with release times

This paper attempts to solve a single machine‐scheduling problem, in which the objective function is to minimize the total weighted tardiness with different release dates of jobs. To address this scheduling problem, a heuristic scheduling algorithm is presented. A mathematical programming formulation is also formulated to validate the performance of the heuristic scheduling algorithm proposed herein. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. Overall, this algorithm can find the optimal solutions for 2200 out of 2400 randomly generated problems (91.67%). For the most complicated 20 job cases, it requires less than 0.0016 s to obtain an ultimate or even optimal solution. This heuristic scheduling algorithm can therefore efficiently solve this kind of problem.     

基于改进遗传算法的单机成组作业调度

提出了单机成组作业调度的改进遗传算法。优化目标为总流程时间的单机成组作业调度问题明显是NP-hard问题,此问题的多项式求解方法不能求取最优解,而一些启发式算法也只能求出此问题的次优解。为获得单机成组作业最优调度,通过采用整数实值编码,随机采样选择,单点交叉以及变异检查,设计了单机成组作业调度的改进遗传算法。仿真结果表明,算法能够找到此问题的最优解,其性能优于加权最短加工时间(WSPT)启发式算法。改进遗传算法能够灵活解决各种单目标调度及多目标调度问题。     

Bi-criteria minimization for the permutation flowshop scheduling problem with machine-based learning effects

In traditional scheduling problems, the processing time for the given job is assumed to be a constant regardless of whether the job is scheduled earlier or later. However, the phenomenon named “learning effect” has extensively been studied recently, in which job processing times decline as workers gain more experience. This paper discusses a bi-criteria scheduling problem in an m-machine permutation flowshop environment with varied learning effects on different machines. The objective of this paper is to minimize the weighted sum of the total completion time and the makespan. A dominance criterion and a lower bound are proposed to accelerate the branch-and-bound algorithm for deriving the optimal solution. In addition, the near-optimal solutions are derived by adapting two well-known heuristic algorithms. The computational experiments reveal that the proposed branch-and-bound algorithm can effectively deal with problems with up to 16 jobs, and the proposed heuristic algorithms can yield accurate near-optimal solutions.     

Two-machine no-wait flowshop scheduling with learning effect and convex resource-dependent processing times

Two-machine no-wait flowshop scheduling problems in which the processing time of a job is a function of its position in the sequence and its resource allocation are considered in the study. The primary objective is to find the optimal sequence of jobs and the optimal resource allocation separately. Here we propose two separate models: minimizing a cost function of makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function of makespan, total waiting time, total absolute differences in waiting times and total resource cost. Since each model is strongly NP-hard, we solve both models by breaking them down to two sub-problems, the optimal resource allocation problem for any job sequence and the optimal sequence problem with its optimal resource allocation. Specially, we transform the second sub-problem into the minimum of the bipartite graph optimal matching problem (NP-hard), and solve it by using the classic KM (Kuhn–Munkres) algorithm. The solutions of the two sub-problems demonstrate that the target problems remain polynomial solvable under the proposed model.     

The total adjustment cost problem: Applications,models, and solution algorithms

Resource leveling problems arise whenever it is expedient to reduce the fluctuations in resource utilization over time, while maintaining a prescribed project completion deadline. Several resource leveling objective functions may be defined, consideration of which results in well-balanced resource profiles. In this paper, we concentrate on a special objective function that determines the costs arising from increasing or decreasing the resource utilizations. The resulting total adjustment cost problem occurs, for example, in the construction industry and can be formulated using mixed-integer linear programming models. Apart from a discrete time-based formulation, two polynomial formulations, namely an event-based model and a start-based model, which exploit structural properties of the problem are presented. In addition, a heuristic solution algorithm is proposed to generate start solutions for the problem. We use CPLEX 12.4 to solve medium-scale instances known from the literature. A computational performance analysis shows that the discrete time-based model and the start-based model are suitable for practical applications.     

Minimizing total completion time for re-entrant flow shop scheduling problems

In this paper, we study re-entrant flow shop scheduling problems with the objective of minimizing total completion time. In a re-entrant scheduling problem, jobs may visit some machines more than once for processing. The problem is NP-hard even for machine number m=2. A heuristic algorithm is presented to solve the problem, in which an effective k-insertion technique is introduced as the improvement strategy in iterations. Computational experiments and analyses are performed to give guidelines of choosing parameters in the algorithm. We also provide a lower bound for the total completion time of the optimal solution when there are only two machines. Objective function values of the heuristic solutions are compared with the lower bounds to evaluate the efficiency of the algorithm. For randomly generated instances, the results show that the given heuristic algorithm generates solutions with total completion times within 1.2 times of the lower bounds in most of the cases.     

一种用于车间作业调度问题的智能枚举算法

车间作业调度问题是优化组合中一个著名的难题,即使规模不大的算例,优化算法的时间也很长。文章提出了一种求解车间作业调度问题的快速智能枚举算法,选取了22个标准算例作为算法的测试试验集,该算法在较短的时间内找到了17个算例的最优解,试验结果表明智能枚举算法确实是一种快速的、有效的求解车间作业调度问题的近似算法。     

Using a branch-and-bound and a genetic algorithm for a single-machine total late work scheduling problem

Scheduling with learning effects has received a lot of research attention lately. On the other hand, it is commonly seen that time restrictions are usually modeled by due dates or deadlines and the quality of schedules is estimated with reference to these parameters. One of the performance measures involving due dates is the late work criterion, which is relatively unexplored. Thus, we study a single-machine scheduling problem with a position-based learning effect. The objective is to minimize the total late work, where the late work for a job is the amount of processing of this job that is performed after its due date. We attempt to develop a branch-and-bound algorithm incorporating with some dominance rules and a lower bound for the optimal solution. For saving computational time, we also propose three heuristic-based genetic algorithms for the near-optimal solution. Finally, the computational results of proposed algorithms are also provided.     

The two-machine flowshop no-wait scheduling problem with a single server to minimize the total completion time

This work studies the scheduling problem where a set of jobs are available for processing in a no-wait and separate setup two-machine flow shop system with a single server. The no-wait constraint requires that the operations of a job have to be processed continuously without waiting between two machines. The setup time is incurred and attended by a single sever which can perform one setup at a time. The performance measure considered is the total completion time. The problem is strongly NP-hard. Optimal solutions for several restricted cases and some properties for general case are proposed. Both the heuristic and the branch and bound algorithms are established to tackle the problem. Computational experiments indicate that the heuristic and the branch and bound algorithm are superior to the existing ones in term of solution quality and number of branching nodes, respectively.     

A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes

This paper investigates the scheduling problem of parallel identical batch processing machines in which each machine can process a group of jobs simultaneously as a batch. Each job is characterized by its size and processing time. The processing time of a batch is given by the longest processing time among all jobs in the batch. Based on developing heuristic approaches, we proposed a hybrid genetic heuristic (HGH) to minimize makespan objective. To verify the performance of our algorithm, comparisons are made through using a simulated annealing (SA) approach addressed in the literature as a comparator algorithm. Computational experiments reveal that affording the knowledge of problem through using heuristic procedures, gives HGH the ability of finding optimal or near optimal solutions in a reasonable time.     

A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs

We present a single-machine problem with the unequal release times under learning effect and deteriorating jobs when the objective is minimizing the makespan. In this study, we introduced a scheduling model with unequal release times in which both job deterioration and learning exist simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 30 jobs, and the average error percentage of the proposed heuristic is less than 0.16%.