On flowshop scheduling problems with the aging effect and resource allocation

In this paper, we focus on real-life settings that require the development of new models of flowshop scheduling problems, where job processing times can increase with the number of processed jobs due to the aging effect and decrease by the allocation of additional resource. We analyse the makespan minimization flowshop problem with such model and also with the aging effect only. We prove that the considered problems and their special cases are still polynomially solvable under given conditions, and on their basis, we provide optimal polynomial time solution algorithms.     

Multiple common due dates assignment and scheduling problems with resource allocation and general position-dependent deterioration effect

This paper investigates the single-machine multiple common due dates assignment and scheduling problems in which the processing time of a job depends on its position in a job sequence and its resource allocation. We examine the general position-dependent deterioration effect and two models of resource allocation. The objective function is to minimize a total penalty function containing earliness, tardiness, due date, and resource consumption costs. We introduce two polynomial time algorithms to solve the considered problems. Since the two algorithms solve the problems in polynomial time, they can solve large-scale instances of the problem under study in little time.     

Some single-machine scheduling problems with the extended sum-of-processing-time-based aging effect

In this paper, we analyze some single machine scheduling problems with the aging effect. We extend the sum-of-processing-time-based aging model such that the fatigue caused by each job to the machine is equal to a non-increasing function dependent on the normal processing time of a job and the aging effect is job dependent. Although the proposed model is more general and describes more precisely the real-life settings, we show that the special cases of the maximum completion time and the maximum lateness minimization problems with this model are still polynomially solvable. However, we prove the maximum completion time minimization problem with the sum-of-processing-time-based aging model is strongly NP-hard if some jobs have deadlines and constant processing times. On this basis, we show that the maximum lateness minimization problem with this aging model is also strongly NP-hard.     

A two-machine flowshop maximum tardiness scheduling problem with a learning effect

The primary objective of this paper is to study a two-machine flowshop scheduling problem with a learning effect where the goal is to find a sequence that minimizes the maximum tardiness. We employ a branch-and-bound method and a simulated annealing (SA) method to search for the optimal solution and a near-optimal solution, respectively. Computational results, using Fisher’s (Math Program 11:229–251 1971) framework, show that the mean and maximum number of nodes for the branch-and-bound algorithm decrease when the learning effect is stronger, the value of the tardiness factor is smaller, or the value of the due date range is larger. In addition, comparisons between the SA method and the earliest due date first (EDD) rule are provided for large-job sizes. Results indicate that the percentage of time that the SA solution outperforms the EDD solution decreases as the job size increases and the learning effect becomes greater. Additionally, the SA solution is never worse than the EDD solution.     

自适应粒子群求解资源动态分配项目调度问题

为了解决传统任务资源固定分配难以实现动态与高效调度的问题,建立了任务资源动态分配项目调度的数学模型,给出了任务调度方案的生成算法。为了克服基本粒子群优化算法的早熟收敛问题,平衡其全局与局部搜索能力,提出了一种改进的自适应粒子群优化算法,该算法采用惯性权重因子周期性衰减和改进的变异策略以及不变位交叉法实现粒子的更新。最后对通用标准库进行了测试,结果表明,所建模型和改进算法能够有效地缩短项目工期,提高资源利用率和算法效率。     

Two meta-heuristics for solving a new two-machine flowshop scheduling problem with the learning effect and dynamic arrivals

This paper develops a new mathematical model and proposes two meta-heuristics for solving a two-machine flowshop scheduling problem that minimizes bi-objectives, namely the total idle time and the mean deviation from a common due data. In this paper, we assume the arrival time of jobs is dynamic, in which each job has a time window and can arrive in its time window randomly. We also assume the learning effect on the processing times considering as a position-dependent effect. Since the problem is an NP-hard one, we present a multiobjective genetic algorithm (MOGA) and a multiobjective simulated annealing (MOSA) algorithm to solve the given problems. The computational results confirm that the proposed MOGA has a better solution in comparison with the proposed MOSA, especially in large-sized problems.     

No-wait flowshop scheduling problem to minimize the number of tardy jobs

This research addresses the m-machine no-wait flowshop scheduling problem with the objective of minimizing the number of tardy jobs. The problem is known to be NP-hard even for the two machines, and literature reveals that no heuristics have been developed for this problem. In this paper, we propose an efficient heuristic based on simulated annealing, where we first adapt the single-machine optimal algorithm to our problem to develop two new heuristics, NOTA and NOTM. An improved simulated annealing heuristic, called SA-GI, is then developed by feeding the best performing heuristic among NOTA, NOTM, and EDD into the simulated annealing algorithm. A second proposed heuristic, called SA-IP, further improves the SA-GI solution by using insertion and pair-wise exchange techniques. Based on the computational experiments, the overall relative percentage errors of the heuristic SA, SA-GI, and SA-IP are 8.848, 8.428, and 0.207, respectively. The computational times of the three heuristics are close to each other, and the largest average time is less than one second, and hence, the computational time is not an issue. Therefore, the heuristic SA-IP is the best one.     

Single-machine scheduling problems with release time of jobs depending on resource allocated

This paper considers the single-machine scheduling problems with learning effect and deteriorating jobs. Release time of jobs is a positive and strictly decreasing function about resource consumption. The optimal algorithm is presented for the problem to minimize the makespan with the total resource consumption constraints. Then, for a given sequence, we propose an optimal solution for the problem to minimize the total resource consumption with the makespan constraints.     

A genetic algorithmic approach to multi-objective scheduling in a Kanban-controlled flowshop with intermediate buffer and transport constraints

In this paper, we consider the problem of extended permutation flowshop scheduling with the intermediate buffers. The Kanban flowshop problem considered involves dual-blocking by both part type and queue size acting on machines, as well as on material handling. The objectives considered in this study include the minimization of mean completion time of containers, mean completion time of part types, and the standard deviation of mean completion time of part types. An attempt is made to solve the multi-objective problem by using a proposed genetic algorithm, called the “non-dominated and normalized distance-ranked sorting multi-objective genetic algorithm” (NDSMGA). In order to evaluate the NDSMGA, we have made use of randomly generated flowshop scheduling problems with input and output buffer constraints in the flowshop. The non-dominated solutions for these problems are obtained from each of the existing methods, namely multi-objective genetic local search (MOGLS), elitist non-dominated sorting genetic algorithm (ENGA), gradual priority weighting genetic algorithm (GPWGA), modified MOGLS, and the NDSMGA. These non-dominated solutions are combined to obtain a net non-dominated solution set for a given problem. Contribution in terms of number of solutions to the net non-dominated solution set from each of these algorithms is tabulated, and the results reveal that a substantial number of non-dominated solutions are contributed by the NDSMGA.     

A genetic algorithmic approach to multi-objective scheduling in a kanban-controlled flowshop with intermediate buffer and transport constraints

In this paper, we consider the problem of extended permutation flowshop scheduling with the intermediate buffers. The Kanban flowshop problem considered involves dual-blocking by both part type and queue size acting on machines, as well as on material handling. The objectives considered in this study include the minimization of mean completion time of containers, mean completion time of part types, and the standard deviation of mean completion time of part types. An attempt is made to solve the multi-objective problem by using a proposed genetic algorithm, called the “non-dominated and normalized distanceranked sorting multi-objective genetic algorithm” (NDSMGA). In order to evaluate the NDSMGA, we have made use of randomly generated flowshop scheduling problems with input and output buffer constraints in the flowshop. The non-dominated solutions for these problems are obtained from each of the existing methods, namely multi-objective genetic local search (MOGLS), elitist non-dominated sorting genetic algorithm (ENGA), gradual priority weighting genetic algorithm (GPWGA), modified MOGLS, and the NDSMGA. These non-dominated solutions are combined to obtain a net non-dominated solution set for a given problem. Contribution in terms of number of solutions to the net non-dominated solution set from each of these algorithms is tabulated, and the results reveal that a substantial number of non-dominated solutions are contributed by the NDSMGA.     

An integrated approach to solve tool-part grouping, job allocation and scheduling problems in a flexible manufacturing system

An integrated approach is discussed in this article to solve the sub-problems like tool-part grouping, job allocation on machines and minimization of make-span in a FMS. Tool and part grouping is performed using “principal component analysis”, and tool allocation has been carried out using priority-based approach by developing a potency index. Thereafter, the concept has evolved based on threshold machining time, minimum operation time, and maximum possible operation time to minimize the make-span of the system. In order to validate the result “analysis of variance” has been employed, and on a simulated example the F ratio is enumerated.     

The two-stage assembly flowshop scheduling problem with bicriteria of makespan and mean completion time

In this paper, we address the two-stage assembly flowshop scheduling problem with a weighted sum of makespan and mean completion time criteria, known as bicriteria. Since the problem is NP-hard, we propose heuristics to solve the problem. Specifically, we propose three heuristics; simulated annealing (SA), ant colony optimization (ACO), and self-adaptive differential evolution (SDE). We have conducted computational experiments to compare the performance of the proposed heuristics. It is statistically shown that both SA and SDE perform better than ACO. Moreover, the experiments reveal that SA, in general, performs better than SDE, while SA consumes less CPU time than both SDE and ACO. Therefore, SA is shown to be the best heuristic for the problem.     

Some single-machine scheduling problems with past-sequence-dependent setup times and a general learning effect

This paper considers a single-machine scheduling model with past-sequence-dependent setup times and a general learning effect. It develops a general model with setup times and learning effect considerations where the actual processing time of a job is not only a function of the total actual processing time of the jobs already processed, but also a function of the job’s scheduled position. The paper shows that the single-machine scheduling problems to minimize the makespan and the sum of the kth power of completion times are polynomially solvable under the proposed model. It further shows that the problems to minimize the total weighted completion time and the maximum lateness are polynomially solvable under certain conditions.     

Scheduling and worker assignment problems on hybrid flowshop with cost-related objective function

This paper proposes a colonial competitive algorithm which is improved by variable neighborhood search algorithm for the simultaneous effects of learning and deterioration on hybrid flowshop scheduling with sequence-dependent setup times. By the effects of learning and deterioration, the processing time of a job is determined by position in the sequence and its execution start time. In addition, it is assumed that the processing time of any job depends on the number of workers assigned to the job on a particular stage, and the more workers assigned to a stage, the shorter the job processing time. These additional traits that are added to the scheduling problem coexist in many realistic scheduling situations. This problem consists of two basic questions of job scheduling and worker assignment. Minimization of the earliness, tardiness, makespan, and total worker employing costs is considered as the objective function. To evaluate the performance of the hybrid colonial competitive algorithm, the random key genetic algorithm, immune algorithm, variable neighborhood search, and hybrid simulated annealing metaheuristic presented previously are investigated for comparison purposes, and computational experiments are performed on standard test problems. Results show that our proposed algorithm performs better than the other algorithms for various test problems.     

一类资源负荷均衡问题的优化调度模型及其算法

针对多个独立任务在多个不完全同等的处理机上处理时,处理机的最大负荷为最小的非抢先调度问题,建立了一类资源负荷均衡问题的优化调度模型。该模型引入0-1方案矩阵和时间负荷矩阵,分别描述了独立任务分配问题和负荷调度问题;针对部分处理机不能处理某一个独立任务的情形,假定其单位处理时间负荷趋于无穷大,从而避免优化调度中出现伪解。采用遗传算法对模型进行了求解。为了提高遗传算法的运算效率,采用整数方案描述和二进制间接编码的方法对方案染色体进行编码。最后,通过一个案例对模型和算法的有效性进行了验证。     

Two single-machine scheduling problems with the effects of deterioration and learning

In this paper, we consider two single-machine scheduling problems with the effect of deterioration and learning. In this model, the processing times of jobs are defined as functions of their starting times and positions in a sequence. For the following two objective functions, the weighted sum of completion times and the maximum lateness, this paper gives two heuristics according to the corresponding problems without learning effect. This paper also gives the worst-case error bound for the heuristics and provides computational results to evaluate the performance of the heuristics.     

铁路场站轨道吊动态配置及其与集卡协同调度

为提高铁路场站集装箱装卸效率和减少轨道吊长距离移动,提出"轨道吊—集卡"协同装卸方案,综合考虑集装箱位置、轨道吊重载与空载操作3个因素,构建轨道吊动态配置及其与集卡协同调度的双层优化模型.上层目标为作业均衡率最大化,解决轨道吊任务动态分配问题;下层目标为最小化作业完工时间,协同调度轨道吊与集卡.针对问题自身特点,结合遗...     

A note on single-machine scheduling problems with the effects of deterioration and learning

This paper studies two single-machine scheduling problems with the effect of deterioration and learning. In this model, the processing times of jobs are defined as functions of their starting times and positions in a sequence. For the following two objective functions: the weighted sum of completion times and the maximum lateness, this paper proposes two heuristics according to the corresponding single machine problems without learning effect. This paper also gives the worst-case error bound for the heuristics and provides computational results to evaluate the performance of the heuristics.