Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects

In this paper, we study an unrelated parallel machine scheduling problem with setup time and learning effects simultaneously. The setup time is proportional to the length of the already processed jobs. That is, the setup time of each job is past-sequence-dependent. The objectives are to minimize the total absolute deviation of job completion times and the total load on all machines, respectively. We show that the proposed problem is polynomially solvable. We also discuss two special cases of the problem and show that they can be optimally solved by lower order algorithms.     

Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs

This paper considers single machine scheduling problems with setup times and deteriorating jobs. The setup times are proportional to the length of the already processed jobs, that is, the setup times are past-sequence-dependent (p-s-d). It is assumed that the job processing times are defined by functions dependent on their starting times. The following objectives are considered: the makespan, the total completion time, and the sum of earliness, tardiness, and due-window starting time and size penalties. We propose polynomial time algorithms to solve these problems.     

Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs

This paper considers single machine scheduling problems with setup times and deteriorating jobs. The setup times are proportional to the length of the already processed jobs, that is, the setup times are past-sequence-dependent (p-s-d). It is assumed that the job processing times are defined by functions dependent on their starting times. The following objectives are considered: the makespan, the total completion time, and the sum of earliness, tardiness, and due-window starting time and size penalties. We propose polynomial time algorithms to solve these problems.     

Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability

This article considers the unrelated parallel machine scheduling problem with sequence- and machine-dependent setup times and machine-dependent processing times. Furthermore, the machine has a production availability constraint to each job. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines to minimize the total completion time. To solve the problem, a mathematical model for the optimal solution is derived, and hybrid genetic algorithms with three dispatching rules are proposed for large-sized problems. To assess the performance of the algorithms, computational experiments are conducted and evaluated using several randomly generated examples.     

Single machine scheduling with past-sequence-dependent setup times and learning effects

This paper studies a single machine scheduling problem with setup times and learning considerations. The setup times are proportional to the length of the already scheduled jobs. That is, the setup times are past-sequence-dependent. It is assumed that the learning process reflects a decrease in the process time as a function of the number of repetitions, i.e., as a function of the job position in the sequence. The following objectives are considered: the makespan, the total completion time, the total absolute differences in completion times and the sum of earliness, tardiness and common due-date penalty. Polynomial time algorithms are proposed to optimally solve the above objective functions.     

带有线性恶化工件和释放时间的两个代理单机调度问题

研究了带有简单线性恶化工件和释放时间的两个代理单机调度问题. 所有工件在一台机器上加工, 每个代理有各自依赖于自己工件的优化目标. 针对工件释放时间相同与不同两种情况, 研究了有约束的优化模型, 即找到调度最小化一个代理的目标函数而使得另一个代理的目标函数不超过一个给定的上界. 当工件具有相同的释放时间, 我们主要考虑的目标函数有: 总加权完工时间和总加权拖期工件数. 当工件具有不同释放时间, 我们考虑的目标函数有: 最大完工时间、总完工时间以及拖期工件数. 对于每一个问题, 我们分析了问题的计算复杂性. 此外, 对于NP难问题的一些特殊情况本文分析了最优解性质, 基于这些性质给出了最优算法.     

Makespan minimization on single batch-processing machine via ant colony optimization

This paper investigates the problem of minimizing makespan on a single batch-processing machine, and the machine can process multiple jobs simultaneously. Each job is characterized by release time, processing time, and job size. We established a mixed integer programming model and proposed a valid lower bound for this problem. By introducing a definition of waste and idle space (WIS), this problem is proven to be equivalent to minimizing the WIS for the schedule. Since the problem is NP-hard, we proposed a heuristic and an ant colony optimization (ACO) algorithm based on the theorems presented. A candidate list strategy and a new method to construct heuristic information were introduced for the ACO approach to achieve a satisfactory solution in a reasonable computational time. Through extensive computational experiments, appropriate ACO parameter values were chosen and the effectiveness of the proposed algorithms was evaluated by solution quality and run time. The results showed that the ACO algorithm combined with the candidate list was more robust and consistently outperformed genetic algorithm (GA), CPLEX, and the other two heuristics, especially for large job instances.     

Two-stage hybrid batching flowshop scheduling with blocking and machine availability constraints using genetic algorithm

This research investigates a two-stage hybrid flowshop scheduling problem in a metal-working company. The first stage consists of multiple parallel machines and the second stage has only one machine. Four characteristics of the company have substantiated the complexity of the problem. First, all machines in stage one are able to process multiple jobs simultaneously but the jobs must be sequentially set up one after another. Second, the setup time of each job is separated from its processing time and depends upon its preceding job. Third, a blocking environment exists between two stages with no intermediate buffer storage. Finally, machines are not continuously available due to the preventive maintenance and machine breakdown. Two types of machine unavailability, namely, deterministic case and stochastic case, are identified in this problem. The former occurs on stage-two machine with the start time and the end time known in advance. The latter occurs on one of the parallel machine in stage one and a real-time rescheduling will be triggered. Minimizing the makespan is considered as the objective to develop the optimal scheduling algorithm. A genetic algorithm is used to obtain a near-optimal solution. The computational results with actual data are favorable and superior over the results from existing manual schedules.     

一类线性加工时间单机调度问题

讨论一类线性加工时间单机调度问题.在这类问题中,工件具有相同的基本加工时间, 但每个工件的实际加工时间以其开工时间线性增长.对满足无延迟工件条件下极小化提前惩罚 和问题,满足最大完工时间限制条件下极小化资源消耗总量的问题和满足资源消耗总量限制条 件下极小化最大完工时间的问题,分别给出了最优算法.     

释放时间和工期同序的单机连续型批调度问题

本文研究的连续型批处理机调度问题, 是在钢铁工业管坯的加热过程中提出来的. 工件带有释放时间和工期, 工件进入和离开机器是按周期依次进行的. 本文针对单机连续型批调度问题中工件释放时间和工期同序的情况, 分析了极小化最大拖期和拖期工件数等问题的计算复杂性, 证明了两类问题都是强NP-难的. 对于工件的释放时间和加工时间、工期都同序的特殊情况, 分别给出了能够获得对应问题的最优解的多项式算法.     

Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints

This paper presents a novel, two-level mixed-integer programming model of scheduling N jobs on M parallel machines that minimizes bi-objectives, namely the number of tardy jobs and the total completion time of all the jobs. The proposed model considers unrelated parallel machines. The jobs have non-identical due dates and ready times, and there are some precedence relations between them. Furthermore, sequence-dependent setup times, which are included in the proposed model, may be different for each machine depending on their characteristics. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches or optimization tools is extremely difficult. This paper proposes an efficient genetic algorithm (GA) to solve the bi-objective parallel machine scheduling problem. The performance of the presented model and the proposed GA is verified by a number of numerical experiments. The related results show the effectiveness of the proposed model and GA for small and large-sized problems.     

Two-machine flowshop scheduling with job class setups to minimize total flowtime

This paper studies the two-machine flowshop scheduling problem with job class setups to minimize the total flowtime. The jobs are classified into classes, and a setup is required on a machine if it switches processing of jobs from one class to another class, but no setup is required if the jobs are from the same class. For some special cases, we derive a number of properties of the optimal solution, based on which we design heuristics and branch-and-bound algorithms to solve these problems. Computational results show that these algorithms are effective in yielding near-optimal or optimal solutions to the tested problems.     

Multi-criteria sequence-dependent job shop scheduling using genetic algorithms

Real world job shops have to contend with jobs due on different days, material ready times that vary, reentrant workflows and sequence-dependent setup times. The problem is even more complex because businesses often judge solution goodness according to multiple competing criteria. Producing an optimal solution would be time consuming to the point of rendering the result meaningless. Commonly used heuristics such as shortest processing time (SPT) and earliest due date (EDD) can be used to calculate a feasible schedule quickly, but usually do not produce schedules that are close to optimal in these job shop environments. We demonstrate that genetic algorithms (GA) can be used to produce solutions in times comparable to common heuristics but closer to optimal. Changing criteria or their relative weights does not affect the running time, nor does it require programming changes. Therefore, a GA can be easily applied and modified for a variety of production optimization criteria in a job shop environment that includes sequence-dependent setup times.     

Single-machine batch scheduling to minimize the total setup cost in the presence of deadlines

We address the single-machine batch scheduling problem with the objective of minimizing the total setup cost. This problem arises when there are n jobs that are partitioned into F families and when setup operations are required whenever the machine switches from processing a job of one family to processing a job of another family. We assume that setups do not require time but are associated with a fixed cost which is identical for all setup operations. Each job has a processing time and an associated deadline. The objective is to schedule all jobs such that they are on time with respect to their deadlines and the total setup cost is minimized. We show that the decision version of this problem is NP-complete in the strong sense. Furthermore, we present properties of optimal solutions and an \(O(n\log n+nF)\) algorithm that approximates the cost of an optimal schedule by a factor of F. The algorithm is analyzed in computational tests.     

Parallel-machine scheduling to minimize tardiness penalty and power cost

Traditional research on machine scheduling focuses on job allocation and sequencing to optimize certain objective functions that are defined in terms of job completion times. With regard to environmental concerns, energy consumption becomes another critical issue in high-performance systems. This paper addresses a scheduling problem in a multiple-machine system where the computing speeds of the machines are allowed to be adjusted during the course of execution. The CPU adjustment capability enables the flexibility for minimizing electricity cost from the energy saving aspect by sacrificing job completion times. The decision of the studied problem is to dispatch the jobs to the machines as well as to determine the job sequence and processing speed of each machine with the objective function comprising of the total weighted job tardiness and the power cost. We give a formal formulation, propose two heuristic algorithms, and develop a particle swarm optimization (PSO) algorithm to effectively tackle the problem. Since the existing solution representations do not befittingly encode the decisions involved in the studied problem into the PSO algorithm, we design a tailored encoding scheme which can embed all decisional information in a particle. A computational study is conducted to investigate the performances of the proposed heuristics and the PSO algorithm.     

Scheduling jobs on a single serial-batching machine with dynamic job arrivals and multiple job types

This paper investigates a scheduling model with certain co-existing features of serial-batching, dynamic job arrival, multi-types of job, and setup time. In this proposed model, the jobs of all types are first partitioned into serial batches, which are then processed on a single serial-batching machine with an independent constant setup time for each new batch. In order to solve this scheduling problem, we divide it into two phases based on job arrival times, and we also derive and prove certain constructive properties for these two phases. Relying on these properties, we develop a two-phase hybrid algorithm (TPHA). In addition, a valid lower bound of the problem is also derived. This is used to validate the quality of the proposed algorithm. Computational experiments, both with small- and large-scale problems, are performed in order to evaluate the performance of TPHA. The computational results indicate that TPHA outperforms seven other heuristic algorithms. For all test problems of different job sizes, the average gap percentage between the makespan, obtained using TPHA, and the lower bound does not exceed 5.41 %.     

Batching and scheduling in a multi-machine flow shop

We study the problem of batching and scheduling n jobs in a flow shop comprising m, m≥2, machines. Each job has to be processed on machines 1,…,m in this order. Batches are formed on each machine. A machine dependent setup time precedes the processing of each batch. Jobs of the same batch are processed on each machine sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs of the same batch formed on machine l become available for a downstream operation on machine l+1 at the same time when the processing of the last job of the batch on machine l has been finished. The objective is to minimize maximum job completion time. We establish several properties of an optimal schedule and develop polynomial time algorithms for important special cases. They are improvements over the existing methods with regard to their generality and time efficiency.     

周期性和事件驱动的JobShop滚动调度策略

为了适应加工的连续性及环境的变化，借用了预测控制中的滚动优化思想提出了周期性和事件驱动的滚动调度策略。调度算法将遗传算法和分派规则相结合，以此来处理与操作序列有关的工件安装时 间和工件到期时间约束的复杂调度问题。     

A charging-scheme decision model for electric vehicle battery swapping station using varied population evolutionary algorithms

This paper proposes a new battery swapping station (BSS) model to determine the optimized charging scheme for each incoming Electric Vehicle (EV) battery. The objective is to maximize the BSS’s battery stock level and minimize the average charging damage with the use of different types of chargers. An integrated objective function is defined for the multi-objective optimization problem. The genetic algorithm (GA), differential evolution (DE) algorithm and three versions of particle swarm optimization (PSO) algorithms have been implemented to solve the problem, and the results show that GA and DE perform better than the PSO algorithms, but the computational time of GA and DE are longer than using PSO. Hence, the varied population genetic algorithm (VPGA) and varied population differential evolution (VPDE) algorithm are proposed to determine the optimal solution and reduce the computational time of typical evolutionary algorithms. The simulation results show that the performances of the proposed algorithms are comparable with the typical GA and DE, but the computational times of the VPGA and VPDE are significantly shorter. A 24-h simulation study is carried out to examine the feasibility of the model.     

Heuristics for the two‐machine scheduling problem with a single server

In this paper, the NP‐hard two‐machine scheduling problem with a single server is addressed. The problem consists of a given set of jobs to be scheduled on two identical parallel machines, where each job must be processed on one of the machines, and prior to processing, the job is set up on its machine using one server; the latter is shared between the two machines. An ant colony optimization (ACO) algorithm is introduced for the problem and its performance was assessed by comparing with an exact solution (branch and bound [B&B]), a genetic algorithm (GA), and simulated annealing (SA). The computational results reflected the superiority of “ACO” in large problems, with a performance similar to SA and GA in smaller problems, while solving the tested problems within a reasonable computational time.