Single machine scheduling problems with resource dependent release times

We consider two single machine scheduling problems with resource dependent release times that can be controlled by a non-increasing convex resource consumption function. In the first problem, the objective is to minimize the total resource consumption with a constraint on the sum of job completion times. We show that a recognition version of the problem is NP-complete. In the second problem, the objective is to minimize the weighted total resource consumption and sum of job completion times with an initial release time greater than the total processing times. We provide some optimality conditions and show that the problem is polynomially solvable.     

A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine

This paper deals with the single machine scheduling problem to minimize the total weighted tardiness in the presence of sequence dependent setup. Firstly, a mathematical model is given to describe the problem formally. Since the problem is NP-hard, a general variable neighborhood search (GVNS) heuristic is proposed to solve it. Initial solution for the GVNS algorithm is obtained by using a constructive heuristic that is widely used in the literature for the problem. The proposed algorithm is tested on 120 benchmark instances. The results show that 37 out of 120 best known solutions in the literature are improved while 64 instances are solved equally. Next, the GVNS algorithm is applied to single machine scheduling problem with sequence dependent setup times to minimize the total tardiness problem without changing any implementation issues and the parameters of the GVNS algorithm. For this problem, 64 test instances are solved varying from small to large sizes. Among these 64 instances, 35 instances are solved to the optimality, 16 instances' best-known results are improved, and 6 instances are solved equally compared to the best-known results. Hence, it can be concluded that the GVNS algorithm is an effective, efficient and a robust algorithm for minimizing tardiness on a single machine in the presence of setup times.     

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.     

A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan

This paper considers the problem of scheduling a set of jobs subject to arbitrary release dates and sequence-dependent setup times on a single machine with the objective of minimizing the maximum completion of all the jobs, or makespan. This problem is often found in manufacturing processes such as painting and metalworking. A new mixed integer linear program (MILP) is firstly proposed. Because the problem is known to be NP-hard, a beam search heuristic is developed. Computational experiments are carried out using a well-known set of instances from the literature. Our results show that the proposed heuristic is effective in finding high quality solutions at low computational cost.     

Lot scheduling on a single machine

In a practical situation, a manufacturer receives different orders from its customers. Different orders may contain different quantities of the product. Therefore, the manufacturer has to decide how to group these orders into different lots based on the capacity of the lot processing machine (such as integrated circuit tester, heated container, etc.) and then decides the sequence of these lots. In this paper, we study a lot scheduling problem with orders which can be split. The objective is to minimize the total completion time of all orders. We show that this problem can be solved in polynomial time.     

Robust single machine scheduling for minimizing total flow time in the presence of uncertain processing times

This research deals with the single machine scheduling problem (SMSP) with uncertain job processing times. The single machine robust scheduling problem (SMRSP) aims to obtain robust job sequences with minimum worst-case total flow time. We describe uncertain processing times using intervals, and adopt an uncertainty set that incorporates a budget parameter to control the degree of conservatism. A revision of the uncertainty set is also proposed to address correlated uncertain processing times due to a number of common sources of uncertainty. A mixed integer linear program is developed for the SMRSP, where a linear program for determining the worst-case total flow time is integrated within the conventional integer program of the SMSP. To efficiently solve the SMRSP, a simple iterative improvement (SII) heuristic and a simulated annealing (SA) heuristic are developed. Experimental results demonstrate that the proposed SII and SA heuristics are effective and efficient in solving SMRSP with practical problem sizes.     

Single machine batch scheduling to minimize total completion time and resource consumption costs

In this paper we study the single-machine batch scheduling problem under batch availability, where both setup and job processing times are controllable by allocating a continuously divisible nonrenewable resource. Under batch availability a set of jobs is processed contiguously and completed together, when the processing of the last job in the batch is finished. We present polynomial time algorithms to find the job sequence, the partition of the job sequence into batches and the resource allocation, which minimize the total completion time or the total production cost (inventory plus resource costs).     

Multi-agent based approach for single machine scheduling with sequence-dependent setup times and machine maintenance

Scheduling of single machine in manufacturing systems is especially complex when the order arrivals are dynamic. The complexity of the problem increases by considering the sequence-dependent setup times and machine maintenance in dynamic manufacturing environment. Computational experiments in literature showed that even solving the static single machine scheduling problem without considering regular maintenance activities is NP-hard. Multi-agent systems, a branch of artificial intelligence provide a new alternative way for solving dynamic and complex problems. In this paper a collaborative multi-agent based optimization method is proposed for single machine scheduling problem with sequence-dependent setup times and maintenance constraints. The problem is solved under the condition of both regular and irregular maintenance activities. The solutions of multi-agent based approach are compared with some static single machine scheduling problem sets which are available in the literature. The method is also tested under real-time manufacturing environment where computational time plays a critical role during decision making process.     

Robust scheduling on a single machine to minimize total flow time

In a real-world manufacturing environment featuring a variety of uncertainties, production schedules for manufacturing systems often cannot be executed exactly as they are developed. In these environments, schedule robustness that guarantees the best worst-case performance is a more appropriate criterion in developing schedules, although most existing studies have developed optimal schedules with respect to a deterministic or stochastic scheduling model. This study concerns robust single machine scheduling with uncertain job processing times and sequence-dependent family setup times explicitly represented by interval data. The objective is to obtain robust sequences of job families and jobs within each family that minimize the absolute deviation of total flow time from the optimal solution under the worst-case scenario. We prove that the robust single machine scheduling problem of interest is NP-hard. This problem is reformulated as a robust constrained shortest path problem and solved by a simulated annealing-based algorithmic framework that embeds a generalized label correcting method. The results of numerical experiments demonstrate that the proposed heuristic is effective and efficient for determining robust schedules. In addition, we explore the impact of degree of uncertainty on the performance measures and examine the tradeoff between robustness and optimality.     

Single CNC machine scheduling with controllable processing times to minimize total weighted tardiness

Advanced manufacturing technologies, such as CNC machines, require significant investments, but also offer new capabilities to the manufacturers. One of the important capabilities of a CNC machine is the controllable processing times. By using this capability, the due date requirements of customers can be satisfied much more effectively. Processing times of the jobs on a CNC machine can be easily controlled via machining conditions such that they can be increased or decreased at the expense of tooling cost. Since scheduling decisions are very sensitive to the processing times, we solve the process planning and scheduling problems simultaneously. In this study, we consider the problem of scheduling a set of jobs on a single CNC machine to minimize the sum of total weighted tardiness, tooling and machining costs. We formulated the joint problem, which is NP-hard since the total weighted tardiness problem (with fixed processing times) is strongly NP-hard alone, as a nonlinear mixed integer program. We proposed a DP-based heuristic to solve the problem for a given sequence and designed a local search algorithm that uses it as a base heuristic.     

A bicriteria approach to minimize maximal lateness and resource consumption for scheduling a single machine

We extend the classical single-machine maximal lateness scheduling problem to the case where the job processing times are controllable by allocating a continuous and nonrenewable resource to the processing operations. Our aim is to construct an efficient trade-off curve between maximal lateness and total resource consumption using a bicriteria approach. We present a polynomial time algorithm that constructs this trade-off curve assuming a specified general type of convex decreasing resource consumption function. We illustrate the algorithm with a numerical example.     

Single machine due-date scheduling of jobs with decreasing start-time dependent processing times

We study the problem of scheduling jobs whose processing times are decreasing functions of their starting times. We consider the case of a single machine and a common decreasing rate for the processing times. The problem is to determine an optimal combination of the due date and schedule so as to minimize the sum of due date, earliness and tardiness penalties. We give an O(n log n) time algorithm to solve this problem.     

Single machine scheduling with precedence constraints and positionally dependent processing times

In many real-life situations the processing conditions in scheduling models cannot be viewed as given constants since they vary over time thereby affecting actual durations of jobs. We consider single machine scheduling problems of minimizing the makespan in which the processing time of a job depends on its position (with either cumulative deterioration or exponential learning). It is often found in practice that some products are manufactured in a certain order implied, for example, by technological, marketing or assembly requirements. This can be modeled by imposing precedence constraints on the set of jobs. We consider scheduling models with positional deterioration or learning under precedence constraints that are built up iteratively from the prime partially ordered sets of a bounded width (this class of precedence constraints includes, in particular, series-parallel precedence constraints). We show that objective functions of the considered problems satisfy the job module property and possess the recursion property. As a result, the problems under consideration are solvable in polynomial time.     

A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times

We present a systematic comparison of hybrid evolutionary algorithms (HEAs), which independently use six combinations of three crossover operators and two population updating strategies, for solving the single machine scheduling problem with sequence-dependent setup times. Experiments show the competitive performance of the combination of the linear order crossover operator and the similarity-and-quality based population updating strategy. Applying the selected HEA to solve 120 public benchmark instances of the single machine scheduling problem with sequence-dependent setup times to minimize the total weighted tardiness widely used in the literature, we achieve highly competitive results compared with the exact algorithm and other state-of-the-art metaheuristic algorithms in the literature. Meanwhile, we apply the selected HEA in its original form to deal with the unweighted 64 public benchmark instances. Our HEA is able to improve the previous best known results for one instance and match the optimal or the best known results for the remaining 63 instances in a reasonable time.     

Integrated production and preventive maintenance scheduling for a single machine with failure uncertainty

This paper addresses the problem of finding a robust and stable schedule for a single machine with availability constraints. The machine suffers unexpected breakdowns and follows the Weibull failure function. A joint model for integrating run-based preventive maintenance (PM) into the production scheduling problem is proposed, in which the sequence of jobs, the PM times and the planned completion times of jobs are proactively determined simultaneously. Aiming at optimizing the bi-objective of system robustness and stability, a genetic algorithm based on the properties of the optimal schedule is proposed. The experimental results demonstrate that the proposed algorithm is efficient and effective under practical problem sizes. In addition, the impact of degree of uncertainty on the performance and the tradeoff between robustness and stability are explored in detail.     

一类具有资源约束和恶化效应的单机成组排序问题

讨论具有连续资源的单机成组排序问题.这一模型中同一组内的工件不允许分开加工,各工件组的安装时间是所消耗资源的非负减少连续函数.工件的加工时问是开工时问的严格减少函数.针对满足资源消耗总量限制条件下极小化最大完工时问的问题.以及在满足最大完工时间限制条件下极小化资源消耗总量的问题,讨论了最优排序的某些特征,分别给出了求解最优资源分配的方法.最后通过数值例子表明了所提出方法的正确性和有效性.     

并行机成组调度问题的启发式算法

研究了优化目标为总拖后/提前时间最小化的并行机成组调度问题,提出了一种三阶段启发式近似求解算法。首先把并行机问题看成单机问题,以最小化总拖后时间为优化目标排列工件的加工次序;然后将工件按第一阶段所求得的次序指派到最先空闲的并行的机器上;最后采用改进的GTW算法对各机器上的工件调度插入适当的空闲时间。计算表明该算法能够在很短的时间内给出大规模调度问题的近似最优解。     

Minimizing worst-case regret of makespan on a single machine with uncertain processing and setup times

This research addresses a single machine scheduling problem with uncertain processing times and sequence-dependent setup times represented by intervals. Our objective is to obtain a robust schedule with the minimum absolute deviation from the optimal makespan in the worst-case scenario. The problem is reformulated as a robust traveling salesman problem (RTSP), whereby a property is utilized to efficiently identify worst-case scenarios. A local search-based heuristic that incorporates this property is proposed to solve the RTSP, along with a simulated annealing-based implementation. The effectiveness and efficiency of the proposed heuristic are compared to those of an exact solution method in the literature.     

Single machine scheduling with batch-dependent setup times

We address a single-machine batch scheduling problem. The setup times (incurred whenever starting a new batch) are assumed to be a function of the number of batches processed previously, i.e., batch-dependent. The objective is minimum total flow-time. We focus on the case of identical processing time jobs. Given the number of jobs and the setup times, we have to determine the optimal number of batches and their (integer) size. An efficient (O(n)) solution procedure is introduced.