Single-machine parallel-batching scheduling with family jobs to minimize weighted number of tardy jobs

We consider the problem of scheduling n jobs in batches on a single parallel-batching machine, where the jobs are partitioned into jobs families and the jobs in each family have the same due date. The objective is to minimize the weighted number of tardy jobs. We first devise an efficient pseudo-polynomial time and a fully polynomial time approximation scheme for the weighted problem. Then we present $O(n^2)$-time and $O(n\log n)$-time algorithms for the case where the jobs have the same weight and for the case where the jobs have the same processing time, respectively.     

Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness

In many realistic production situations, a job processed later consumes more time than the same job when it is processed earlier. Production scheduling in such an environment is known as scheduling with deteriorating jobs. However, research on scheduling problems with deteriorating jobs has rarely considered explicit (separable) setup time (cost). In this paper, we consider a single-machine scheduling problem with deteriorating jobs and setup times to minimize the maximum tardiness. We provide a branch-and-bound algorithm to solve this problem. Computational experiments show that the algorithm can solve instances up to 1000 jobs in reasonable time.     

最小化误工工件个数的两代理单机排序问题

针对研究了两代理情形下的单机排序问题,考虑两类问题：一是在误工工件个数不超过一个给定值的情况下使得总误工最小,另一个是代理[A]的工件加工时间和权重满足反一致关系时,在误工工件个数不超过一个给定值的情况下使得总加权完工时间之和最小。对于这两类问题采用动态规划方法分别给出最优性质和相应的拟多项式时间算法。     

Single-machine scheduling with deteriorating jobs

In this article, we study a single-machine scheduling problem in which the processing time of a job is a nonlinear function of its basic processing time and starting time. The objectives are to minimise the makespan, the sum of weighted completion times and the sum of the kth powers of completion times. We show that the makespan minimisation problem can be solved in polynomial time. However, the total completion time and the sum of the kth powers of completion times minimisation problems can be solved in polynomial time in some cases. Besides, some useful properties are also provided for the sum of weighted completion times problem under certain conditions.     

Scheduling parallel CNC machines with time/cost trade-off considerations

When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. A well-known example for such a case that this paper specifically deals with is the turning operation on a CNC machine. Manufacturing cost of a turning operation is a nonlinear convex function of its processing time. We also know that scheduling decisions are quite sensitive to the processing times. Therefore, this paper considers minimizing total manufacturing cost (_F1)$(F_1)$ and total completion time (_F2)$(F_2)$ objectives simultaneously on identical parallel CNC turning machines. Since decreasing processing time of a job increases its manufacturing cost, we cannot minimize both objectives at the same time, so the problem is to generate non-dominated solutions. We consider the problem of minimizing _F1$F_1$ subject to a given _F2$F_2$ level and give an effective formulation for the problem. For this problem, we prove some optimality properties which facilitated designing an efficient heuristic algorithm to generate approximate non-dominated solutions. Computational results show that proposed algorithm performs almost equal with the GAMS/MINOS commercial solver although it spends much less computation 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.     

Single-machine scheduling with periodic maintenance to minimize makespan

We consider a single-machine scheduling problem with periodic maintenance activities. Although the scheduling problem with maintenance has attracted researchers’ attention, most of past studies considered only one maintenance period. In this research several maintenance periods are considered where each maintenance activity is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the makespan, subject to periodic maintenance and nonresumable jobs. We first prove that the worst-case ratio of the classical LPT   algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case ratio less than 2 unless P=NP$P=\text{<italic>NP</italic>}$, which implies that the LPT algorithm is the best possible.     

Minimizing the number of tardy jobs with stochastically-ordered processing times

We consider the single-machine sequencing model with stochastic processing times and the problem of minimizing the number of stochastically tardy jobs. In general, this problem is NP-hard. Recently, however, van den Akker and Hoogeveen found some special cases that could be solved in polynomial time. We generalize their findings by providing a polynomial time solution for any stochastically ordered processing times.     

求解并行机拖期与能耗成本优化调度的混合教一学算法

针对加工时间可控的并行机调度,提出了一类考虑拖期与能耗成本优化的调度问题。首先对调度问题进行了问题描述,并建立了整数线性规划模型以便于CPLEX求解。为了快速获得问题的满意解,提出了一种混合教-学算法。结合问题的性质,设计了编码与解码方法以克服标准教-学算法无法直接适用于离散问题的缺点。同时,构建了基于变邻域搜索的局部搜索算子以强化混合算法的搜索性能。最后,对加工时间可控的并行机调度问题进行了仿真实验,测试结果验证了本文构建的整数线性规划模型和混合算法的可行性和有效性。     

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

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

Deteriorating job scheduling to minimize the number of late jobs with setup times

Deteriorating jobs scheduling problems have been widely studied recently. However, research on scheduling problems with deteriorating jobs has rarely considered explicit setup times. With the current emphasis on customer service and meeting the promised delivery dates, we consider a single-machine scheduling problem to minimize the number of late jobs with deteriorating jobs and setup times in this paper. We derive some dominance properties, a lower bound, and an initial upper bound by using a heuristic algorithm to speed up the search process of the branch-and-bound algorithm. Computational experiments show that the algorithm can solve instances up to 1000 jobs in a reasonable amount of time.     

Three scheduling problems with deteriorating jobs to minimize the total completion time

In this paper, three scheduling problems with deteriorating jobs to minimize the total completion time on a single machine are investigated. By a deteriorating job, we mean that the processing time of the job is a function of its execution start time. The three problems correspond to three different decreasing linear functions, whose increasing counterparts have been studied in the literature. Some basic properties of the three problems are proved. Based on these properties, two of the problems are solved in O(nlogn) time, where n is the number of jobs. A pseudopolynomial time algorithm is constructed to solve the third problem using dynamic programming. Finally, a comparison between the problems with job processing times being decreasing and increasing linear functions of their start times is presented, which shows that the decreasing and increasing linear models of job processing times seem to be closely related to each other.     

Minimizing the number of tardy jobs on a proportionate flowshop with general position-dependent processing times

In various real life scheduling systems job processing times vary according to the number of jobs previously processed. The vast majority of studies assume a restrictive functional form to describe job processing times. In this note, we address a scheduling problem with the most general job processing time functions. The machine setting assumed is an m-machine proportionate flowshop, and the objective function is minimum number of tardy jobs. We show that the problem can be formulated as a bottleneck assignment problem with a maximum cardinality constraint. An efficient polynomial time (O(n⁴ log n)) solution is introduced.     

Cyclic routing algorithms in graphs: Performance analysis and applications to robot scheduling

In this paper we revisit and extend the algorithm for the cyclic project scheduling problem which was originally proposed by Romanovskii (1967). While the algorithm has been derived for fixed numerical data, we show how it can be extended to handle the problems with interval data. We also propose a new algorithm for the cyclic scheduling problem with interval data that extends the parametric method developed by Megiddo (1979) and runs in strongly polynomial time.     

Single-machine scheduling with past-sequence-dependent setup times and learning effects: a parametric analysis

In this article, we consider the single-machine scheduling problem with past-sequence-dependent (p-s-d) setup times and a learning effect. The setup times are proportional to the length of jobs that are already scheduled; i.e. p-s-d setup times. The learning effect reduces the actual processing time of a job because the workers are involved in doing the same job or activity repeatedly. Hence, the processing time of a job depends on its position in the sequence. In this study, we consider the total absolute difference in completion times (TADC) as the objective function. This problem is denoted as 1/LE, s _psd /TADC in Kuo and Yang (2007 Kuo, WH and Yang, DL. 2007. Single Machine Scheduling with Past-sequence-dependent Setup Times and Learning Effects. Information Processing Letters, 102: 22–26. [Crossref], [Web of Science ®] , [Google Scholar]) (‘Single Machine Scheduling with Past-sequence-dependent Setup Times and Learning Effects’, Information Processing Letters, 102, 22–26). There are two parameters a and b denoting constant learning index and normalising index, respectively. A parametric analysis of b on the 1/LE, s _psd /TADC problem for a given value of a is applied in this study. In addition, a computational algorithm is also developed to obtain the number of optimal sequences and the range of b in which each of the sequences is optimal, for a given value of a. We derive two bounds b* for the normalising constant b and a* for the learning index a. We also show that, when a?a* or b?>?b*, the optimal sequence is obtained by arranging the longest job in the first position and the rest of the jobs in short processing time order.     

Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance

This research focuses on the problem of scheduling jobs on a single machine that requires periodic maintenance with the objective of minimizing the number of tardy jobs. We present a two-phase heuristic algorithm in which an initial solution is obtained first with a method modified from Moore's algorithm for the problem without maintenance and then the solution is improved in the second phase. Performance of the proposed heuristic algorithm is evaluated through computational experiments on randomly generated problem instances and results show that the heuristic gives solutions close to those obtained from a commercial integer programming solver in much shorter time and works better than an existing heuristic algorithm in terms of the solution quality.     

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.     

Two-machine flowshop scheduling with flexible operations and controllable processing times

We consider a two-machine flowshop scheduling problem with identical jobs. Each of these jobs has three operations, where the first operation must be performed on the first machine, the second operation must be performed on the second machine, and the third operation (named as flexible operation) can be performed on either machine but cannot be preempted. Highly flexible CNC machines are capable of performing different operations. Furthermore, the processing times on these machines can be changed easily in albeit of higher manufacturing cost by adjusting the machining parameters like the speed and/or feed rate of the machine. The overall problem is to determine the assignment of the flexible operations to the machines and processing times for each operation to minimize the total manufacturing cost and makespan simultaneously. For such a bicriteria problem, there is no unique optimum but a set of nondominated solutions. Using ?-constraint$?\mathrm{-}\mathrm{constraint}$ approach, the problem could be transformed to be minimizing total manufacturing cost for a given upper limit on the makespan. The resulting single criterion problem can be reformulated as a mixed integer nonlinear problem with a set of linear constraints. We use this formulation to optimally solve small instances of the problem while a heuristic procedure is constructed to solve larger instances in a reasonable time.     

Parallel machine scheduling with fuzzy processing times using a robust genetic algorithm and simulation

This paper addresses parallel machine scheduling problems with fuzzy processing times. A robust genetic algorithm (GA) approach embedded in a simulation model is proposed to minimize the maximum completion time (makespan). The results are compared with those obtained by using the “longest processing time” rule (LPT), which is known as the most appropriate dispatching rule for such problems. This application illustrates the need for efficient and effective heuristics to solve such fuzzy parallel machine scheduling problems (FPMSPs). The proposed GA approach yields good results quickly and several times in one run. Moreover, because it is a search algorithm, it can explore alternative schedules providing the same results. Thanks to the simulation model, several robustness tests are conducted using different random number sets, and the robustness of the proposed approach is demonstrated.