双目标函数下需要安装时间的平行多功能机排序问题

讨论了双目标函数下需要安装时间的平行多功能机排序问题。在该问题中,每个工件对应机器集合的一个子集,且每个工件只能在相应子集中的任一台机器上加工,工件分组,不同组中的工件连续加工需要安装时间,目标函数为极小化最大完工时间和安装次数。根据实际应用背景确定双目标排序问题的形式,并证明了该问题是NP—难的。设计了一个求启发式有效解的算法,首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后逐步改进最大完工时间和拆分工件组,从而得到一系列的启发式有效解。实验表明,该算法是实用而有效的。     

Single machine scheduling with a learning effect and discounted costs

In this paper, we consider a single machine scheduling problem with a learning effect and discounted costs. The learning effect of a job is assumed to be a function of its position. We show that discounted total completion time is minimized by the classical shortest processing time first (SPT) rule. For the following objective function, discounted total weighted completion time, we show by an example that the optimal schedule of the classical discounted weighted shortest processing time first (WDSPT) rule is not optimal in the presence of a learning effect. But for some special cases, we prove that the WDSPT rule can construct the optimal sequence. We give the worst-case error bound for the WDSPT rule in the general case. Some extensions of the problem are also given.     

Single machine scheduling jobs with a truncated sum-of-processing-times-based learning effect

In this note, we consider a single-machine scheduling problem with truncated sum-of-processing-times-based learning considerations. We show that even with the introduction of the proposed model to job processing times, several single-machine problems remain polynomially solvable. For the following objective functions, the discounted total weighted completion time, the maximum lateness, we present heuristics according to the corresponding problems without learning effect. We also analyze the worst-case bound of our heuristics.     

A parallel machine batch scheduling problem in a brewing company

This work introduces a scheduling problem which is motivated from a real situation faced by one of the largest brewing companies in Mexico. Several products must follow a brewing process which is composed by three main stages: coction, fermentation, and conditioning. In the coction stage, there are multiple unrelated parallel machines, and in the fermentation and conditioning stages, there are several heterogeneous tanks. Additionally, during the production process, some maintenance operations must be scheduled. The problem can be seen as a parallel machine batch scheduling problem with sequence-dependent setup times. Due to the complex structure of the problem, we propose a Greedy Randomized Adaptive Search Procedure to generate good quality solutions in a short computation time. Computational experiments are conducted with real and artificial instances. The solutions obtained for the real instances show that the proposed algorithm reaches better solutions than the current solutions generated by the decision maker at the brewery, and the computation time required by our algorithm is dramatically shorter than the one required by the company.     

一类并行机调度问题的动态调度算法

针对不确定制造环境中配件数量约束条件发生变化后的并行机动态调度问题,提出了一种基于操作属性模式的并行机动态调度算法.该算法针对总拖期时间性能指标的优化,根据配件负载的裕量和相邻操作的属性模式,对原调度方案的操作次序和操作上机时间进行了调整.在不同操作和设备规模下,以及不同配件数量变化幅度下进行了数值计算.数值计算结果和实际应用结果表明,该算法是有效的,具有计算复杂度低、实时性好、对原调度算法不敏感的特点.     

Unrelated parallel machine scheduling with secondary resource constraints

This paper considers unrelated parallel machine scheduling with secondary resource constraints. There are n jobs, each needing to be processed on one of the fitted machines. A setup that includes detaching one die and attaching another from the fitted die type is incurred if the type of job scheduled is different from the last job on that machine. For each kind of die type, the number of dies available is limited. Due to the mechanical structure of the machines, the processing time of a job depends on the machine on which the job is processed, and some jobs are restricted to be processed only on certain machines. In this paper, a heuristic with a capability relative to a runtime and solution quality is developed to minimise the makespan. The performance of the presented heuristic is evaluated through extensive computational experiments. Computational results show that the presented heuristic outperforms the search method tested. It is expected that this research can be applied in industry where unrelated parallel machines are used to process different components and setups for auxiliary equipments are required.     

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.     

Workflow balancing strategies in parallel machine scheduling

Workflow balancing on a shop floor helps to remove bottlenecks present in the manufacturing system. Workflow refers to the total time during which the work centres are busy. Idle time is not taken into account when calculating workflow. Earlier researchers have not specified the method for jobs to be executed in parallel in order to balance the workflow to each machine. In many manufacturing environments, multiple processing stations are used in parallel to obtain adequate capacity. In parallel machine scheduling there are m machines to which n jobs are to be assigned based on different priority strategies. The procedure is based on the idea of workload balancing and on balancing the workload among machines. In this paper, workflow and workload are assumed to have the same meaning. A machine with the lowest workflow is selected for assignment of a new job from the list of unfinished jobs. Different priority strategies are followed for the selection of jobs. Three different strategies are considered, namely random (RANDOM), shortest processing time (SPT) and longest processing time (LPT) for the selection of jobs for workflow balancing. The relative percentage of imbalance (RPI) is adopted among the parallel machines to evaluate the performance of these strategies in a standard manufacturing environment. The LPT rule shows better performance for the combination of larger job sizes and higher number of work centres or machines. A computer program was coded for validation in a standard manufacturing environment on an IBM/PC compatible system in the C++ language.     

Solution approaches for a real-life resource-constrained parallel machine scheduling problem

This paper deals with a real-world scheduling problem in an injection-molding department of an electrical appliance plant. In the department, a resource-constrained parallel machine scheduling problem with machine eligibility restrictions is investigated. First, an integer-programming (IP) model with the objective of minimizing makespan is developed for the entire problem. Since this entire IP model has a huge number of variables, it cannot handle the problem efficiently. To obtain more efficient results, two solution approaches, namely IP/IP and IP/constraint programming (CP) both of which partition the entire problem into loading and scheduling sub-problems, are proposed. The loading phase, in which an IP loading model assigns the jobs to machines with the aim of minimizing maximum load on the machines and operators, is the same for both approaches. Subsequently, in the scheduling phase, the IP/IP approach uses an IP scheduling model while the IP/CP approach applies a CP scheduling model to obtain the final schedule of the jobs. Computational results show that the proposed solution methods improve makespan values for almost all test problems in comparison to the entire IP model. In particular, the IP/IP approach performs better in the test problems with greater number of operators, whereas IP/CP approach provides quick and practical results in almost all test problems and gives relatively more efficient makespan values when the resource constraints are tight (i.e., the case of smaller number of operators).     

Dispatching rules for unrelated parallel machine scheduling with release dates

A simplified procedure is proposed to predict the surface integrity of complex-shape parts generated by ball-end finishing milling. Along a complex cutting path, the tool inclination may vary within a large range. A geometrical study is performed to predict the effect of the tool inclination (lead angle) on the micro-geometry of the machined surface and on the effective cutting speed. This geometrical study brings out a range of values of the lead angle for which the machined surface is damaged by cutting pull-outs. This geometrical study also brings out a range of values of the lead angle for which the effective cutting speed is null. This case corresponds to extreme values of the cutting forces and to high compressive residual stresses. These predictions are verified for a selection of tool inclinations and other cutting parameters such as cutting speed, feed per tooth and cusp height. These machining tests are performed on a high-strength bainitic steel. The experimental campaign includes milling tests with cutting forces measurements, 2-D optical micro-geometry measurements and X-ray diffraction measurements.     

Optimal parallel machines scheduling with machine availability and eligibility constraints

In reality, the machine might become unavailable due to machine breakdowns or various inevitable reasons, and machine might have different capability to processing job. Motivated by this, we consider the problem of scheduling n non-preemptive and independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the maximum lateness. Each machine is capable of processing at specific availability intervals. We develop a branch and bound algorithm applying several immediate selection rules for solving this scheduling problem.     

求解具有预防性维护的并行机调度的遗传算法

为了避免设备出现故障对生产造成损失,需对设备进行有效的预防性维护。本文研究了工件带有释放时间的预防性维护的并行机调度问题,以最小化总工期为优化目标。对该问题设计了一个遗传算法进行求解。染色体为工件序列和机器序列,采用最先适配启发式方法确定各工件的最优时间表。数值实验结果表明,本文设计的遗传算法的性能优于简单启发式算法——最短加工时间的最先适配算法,且计算时间是可接受的。     

A hybrid particle swarm optimization for parallel machine total tardiness scheduling

The parallel machine scheduling problem has received increasing attention in recent years. This research considers the problem of scheduling jobs on parallel machines with a total tardiness objective. In the view of its non-deterministic polynomial-time hard nature, the particle swarm optimization (PSO), which is inspired by the swarming or collaborative behavior of biological populations, is employed to solve the parallel machine total tardiness problem (PMTP). Since it is very hard to directly apply standard PSO to this problem, a new solution representation is designed based on real number encoding, which can conveniently convert the job sequences of PMTP to continuous position values. Moreover, in order to enhance the performance of PSO, we introduce clonal selection algorithm (CSA) into PSO and therefore propose a new CSPSO method. The incorporation of CSA can greatly improve the swarm diversity and avoid premature convergence. We further investigate three parameters of PSO and CSPSO, finding that the parameters have marginal impact on CSPSO, which indicates that CSPSO is a very stable and robust method. The performance of CSPSO is evaluated in comparison with traditional genetic algorithm (GA) and standard PSO on 250 benchmark instances. Experimental results show that CSPSO significantly outperforms GA and PSO, with obtaining the optimal solutions of 237 instances. Additionally, PSO appears more effective than GA.     

Ant colony optimization for unrelated parallel machine scheduling

Meeting due dates is a major issue in most manufacturing systems, and one effective measure for due dates is total weighted tardiness. In this research, we consider an ant colony optimization (ACO) algorithm incorporating a number of new ideas (heuristic initial solution, machine reselection step, and local search procedure) to solve the problem of scheduling unrelated parallel machines to minimize total weighted tardiness. The problem is NP-hard in the strong sense, because the single machine case is already NP-hard in the strong sense. Computational results show that the proposed ACO algorithm outperforms other existing algorithms in terms of total weighted tardiness.     

Hybrid metaheuristics for unrelated parallel machine scheduling with sequence-dependent setup times

This paper proposes several hybrid metaheuristics for the unrelated parallel-machine scheduling problem with sequence-dependent setup times given the objective of minimizing the weighted number of tardy jobs. The metaheuristics begin with effective initial solution generators to generate initial feasible solutions; then, they improve the initial solutions by an approach, which integrates the principles of the variable neighborhood descent approach and tabu search. Four reduced-size neighborhood structures and two search strategies are proposed in the metaheuristics to enhance their effectiveness and efficiency. Five factors are used to design 32 experimental conditions, and ten test problems are generated for each condition. Computational results show that the proposed hybrid metaheuristics are significantly superior to several basic tabu search heuristics under all the experimental conditions.     

Dynamic parallel machine scheduling with mean weighted tardiness objective by Q-Learning

In this paper, we discuss a dynamic unrelated parallel machine scheduling problem with sequence-dependant setup times and machine–job qualification consideration. To apply the Q-Learning algorithm, we convert the scheduling problem into reinforcement learning problems by constructing a semi-Markov decision process (SMDP), including the definition of state representation, actions and the reward function. We use five heuristics, WSPT, WMDD, WCOVERT, RATCS and LFJ-WCOVERT, as actions and prove the equivalence of the reward function and the scheduling objective: minimisation of mean weighted tardiness. We carry out computational experiments to examine the performance of the Q-Learning algorithm and the heuristics. Experiment results show that Q-Learning always outperforms all heuristics remarkably. Averaged over all test problems, the Q-Learning algorithm achieved performance improvements over WSPT, WMDD, WCOVERT, RATCS and LFJ-WCOVERT by considerable amounts of 61.38%, 60.82%, 56.23%, 57.48% and 66.22%, respectively.     

A Pareto evolutionary algorithm approach to bi-objective unrelated parallel machine scheduling problems

This paper addresses the unrelated parallel machine scheduling problem with job sequence- and machine-dependent setup times. The preemption of jobs is not permitted, and the optimization criteria are to simultaneously minimize total weighted flow time and total weighted tardiness. The problem has applications in industries such as TFT-LCD, automobile, and textile manufactures. In this study, a Pareto evolutionary approach is proposed to solve the bi-objective scheduling problem. The performance of this approach using different encoding and decoding schemes is evaluated and is compared with that of two multi-objective simulated annealing algorithms via a set of instances generated by a method in the literature. The experimental results indicate that the Pareto evolutionary approach using random key representation and weighted bipartite matching optimization method outperforms the other algorithms in terms of closeness metric, based on similar computation times. Additionally, although the proposed method does not provide the best distribution in terms of diversity metric, it found most of the reference solutions.