Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints

This research deals with scheduling jobs on unrelated parallel machines with auxiliary equipment constraints. Each job has a due date and requires a single operation. A setup for dies is incurred if there is a switch from processing one type of job to another type. For a die type, the number of dies is limited. Due to the attributes of the machines and the fitness of dies to each, the processing time for a job depends on the machine on which the job is processed, each job being restricted to processing on certain machines. In this paper, an effective heuristic based on threshold-accepting methods, tabu lists, and improvement procedures is proposed to minimize total tardiness. An extensive experiment is conducted to evaluate the computational characteristics of the proposed heuristic. Computational experiences demonstrate that the proposed heuristic is capable of obtaining optimal solutions for small-sized problems, and significantly outperforms an ATCS procedure and a simulated annealing method for problems in larger sizes.     

Scheduling dedicated jobs with variative processing times

We consider the following optimization problem. There is a set of \(n\) dedicated jobs that are to be processed on \(m\) parallel machines. The job set is partitioned into subsets and jobs of each subset have a common due date. Processing times of jobs are interconnected and they are the subject of the decision making. The goal is to choose a processing time for each job in a feasible way and to construct a schedule that minimizes the maximum lateness. We show that the problem is NP-hard even if \(m=1\) and that it is NP-hard in the strong sense if \(m\) is a variable. We prove that there is no approximate polynomial algorithm with guaranteed approximation ratio less than 2. We propose an integer linear formulation for the problem and perform experiments. The experiments show that the solutions obtained with CPLEX within the limit of 5 min are on average about 5 % from the optimum value for instances with up to 150 jobs, 16 subsets and 11 machines. Most instances were solved to optimality and the average CPLEX running time was 32 s for these instances.     

Discrete parallel machine makespan ScheLoc problem

Scheduling–Location (ScheLoc) problems integrate the separate fields of scheduling and location problems. In ScheLoc problems the objective is to find locations for the machines and a schedule for each machine subject to some production and location constraints such that some scheduling objective is minimized. In this paper we consider the discrete parallel machine makespan ScheLoc problem where the set of possible machine locations is discrete and a set of n jobs has to be taken to the machines and processed such that the makespan is minimized. Since the separate location and scheduling problem are both \(\mathcal {NP}\)-hard, so is the corresponding ScheLoc problem. Therefore, we propose an integer programming formulation and different versions of clustering heuristics, where jobs are split into clusters and each cluster is assigned to one of the possible machine locations. Since the IP formulation can only be solved for small scale instances we propose several lower bounds to measure the quality of the clustering heuristics. Extensive computational tests show the efficiency of the heuristics.     

2-Distance vertex-distinguishing index of subcubic graphs

This paper addresses the performance of scheduling algorithms for a two-stage no-wait hybrid flowshop environment with inter-stage flexibility, where there exist several parallel machines at each stage. Each job, composed of two operations, must be processed from start to completion without any interruption either on or between the two stages. For each job, the total processing time of its two operations is fixed, and the stage-1 operation is divided into two sub-parts: an obligatory part and an optional part (which is to be determined by a solution), with a constraint that no optional part of a job can be processed in parallel with an idleness of any stage-2 machine. The objective is to minimize the makespan. We prove that even for the special case with only one machine at each stage, this problem is strongly NP-hard. For the case with one machine at stage 1 and m machines at stage 2, we propose two polynomial time approximation algorithms with worst case ratio of \(3-\frac{2}{m+1}\) and \(2-\frac{1}{m+1}\), respectively. For the case with m machines at stage 1 and one machine at stage 2, we propose a polynomial time approximation algorithm with worst case ratio of 2. We also prove that all the worst case ratios are tight.     

On the optimality of the TLS algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines

In this paper we study the optimality of the TLS algorithm for solving the online scheduling problem of minimizing the makespan on a set of m multipurpose machines, where there are two different job types and each job type can only be processed on a unique subset of machines. The literature shows that the TLS algorithm is optimal for the special cases where either m=2 or where all processing times are restricted to unity. We show that the TLS algorithm is optimal also for the special cases where the job processing times are either job type or machine set dependent. For both cases, the optimality of the TLS algorithm is proven by showing that its competitive ratio matches the lower bound for any processing set and processing time parameters.     

Route‐Independent Analysis of Available Capacity in Flexible Manufacturing Systems

In a job shop, because of large setup times, each operation is assigned to only one machine. There is no alternative routing. In a flexible manufacturing system, each manufacturing operation can often be performed on several machines. Therefore, with automated equipment, the capacity of a machine to perform certain operations is not independent of the capacity of other machines. Often, however, operations managers can use a route‐independent answer to production planning questions. For example, how much can be produced of a certain part type and when are important capacity questions in business negotiations, when the detailed routing and scheduling are not yet of interest or cannot be known. This paper provides a mathematical model for the route‐independent analysis of the capacity of flexible manufacturing systems based on a concept of operation types. An example is provided both to illustrate the use of operation types and to highlight the differences between the traditional route‐dependent and the proposed route‐independent formulations of capacity constraints. Some computational results are also given. Finally, a sensitivity analysis is developed to analyze the feasibility of production plans when production requirements and machine capacities can change.     

A two-stage approach for surgery scheduling

A scheduling theory model is applied to study surgery scheduling in hospitals. If a surgical patient is regarded as a job waiting to be processed, and the related surgeons, anesthesiologists, nurses and surgical equipment as machines that are simultaneously needed for the processing of job, then the surgery scheduling can be described as a parallel machines scheduling problem in which a job is processed by multiple machines simultaneously. We adopt the two-stage approach to solve this scheduling problem and develop a computerized surgery scheduling system to handle such a task. This system was implemented in the Shanghai First People’s Hospital and increased the quantity of average monthly finished operations by 10.33 %, the utilization rate of expensive equipment by 9.66 % and the patient satisfaction degree by 1.12 %, and decreased the average length of time that patients wait for surgery by 0.46 day.     

A Multi-Exchange Neighborhood for Minimum Makespan Parallel Machine Scheduling Problems

We propose new local search algorithms for minimum makespan parallel machine scheduling problems, which perform multiple exchanges of jobs among machines. Inspired by the work of Thompson and Orlin (1989) on cyclic transfer neighborhood structures, we model multiple exchanges of jobs as special disjoint cycles and paths in a suitably defined improvement graph, by extending definitions and properties introduced in the context of vehicle routing problems (Thompson and Psaraftis, 1993) and of the capacitated minimum spanning tree problem (Ahuja et al., 2001). Several algorithms for searching the neighborhood are suggested.We report the results of a wide computational experimentation, on different families of benchmark instances, performed for the case of identical machines. This problem has been selected as a case study to perform a comparison among the alternative algorithms, and to discover families of instances for which the proposed neighborhood may be promising in practice. Based on the results of the experiments, we can suggest which among the many possible variants of the proposed approaches may be more promising for developing local search algorithms based on multi-exchange moves for related problems. Also, on some families of instances, which are very hard to solve exactly, the most promising multi-exchange algorithms were observed to dominate, in solution quality and in computational time, competitive benchmark heuristics.     

自动化立体仓库中出入库任务顺序与出库位置选择集成优化研究

具有多个出口的自动化立体仓库系统是一种将存储和分拣相结合的新型仓储技术,其最典型的特征是在货架底层有很多个出库位置以供取货人员分拣。研究此系统中出入库任务排序与出口选择的集成优化问题,以最小化堆垛机完成所有任务的移动距离为目标,将此问题转化为一个混合整数规划模型。根据问题的特点设计了两阶段启发式算法求解此问题,数值结果表明设计的算法能在较短时间内给出近似最优解,同时与企业常用的先到先服务方法相比,该算法可以缩短超过20%的移动距离。     

自动化立体仓库中的储位分配及存取路径优化

储位分配和存取作业路径优化是仓储管理中的两个重要决策问题。本文研究如何在自动化立体仓库中对这两个问题进行同时决策。提出了一个混合整数规划模型对该问题进行优化建模,设计开发了一个基于有向连接图的两阶段优化算法对问题求初始解,并利用禁忌搜索算法对所求得的解进行改进。算法第一阶段解决储位分配问题,在此基础上第二阶段利用Hungarian算法对堆垛机的存取作业路径优化问题进行求解。最后利用实例对算法效率和精度进行分析评价,计算结果验证了算法的有效性。     

On cutting stock with due dates

Classical stock cutting calls for fulfilling a given demand of parts, minimizing raw material needs. With the production of each part type regarded as a job due within a specific date, a problem arises of scheduling cutting operations. We here propose an exact integer linear programming formulation, and develop primal heuristics, upper bounds and an implicit enumeration scheme. A computational experience carried out for the one-dimensional problem shows that our primal heuristics outperform known ones, and that the formulation has good features for finding exact solutions of non-trivial instances.     

Linear solution schemes for Mean-SemiVariance Project portfolio selection problems: An application in the oil and gas industry

We study the Mean-SemiVariance Project (MSVP) portfolio selection problem, where the objective is to obtain the optimal risk-reward portfolio of non-divisible projects when the risk is measured by the semivariance of the portfolio׳s Net-Present Value (NPV) and the reward is measured by the portfolio׳s expected NPV. Similar to the well-known Mean-Variance portfolio selection problem, when integer variables are present (e.g., due to transaction costs, cardinality constraints, or asset illiquidity), the MSVP problem can be solved using Mixed-Integer Quadratic Programming (MIQP) techniques. However, conventional MIQP solvers may be unable to solve large-scale MSVP problem instances in a reasonable amount of time. In this paper, we propose two linear solution schemes to solve the MSVP problem; that is, the proposed schemes avoid the use of MIQP solvers and only require the use of Mixed-Integer Linear Programming (MILP) techniques. In particular, we show that the solution of a class of real-world MSVP problems, in which project returns are positively correlated, can be accurately approximated by solving a single MILP problem. In general, we show that the MSVP problem can be effectively solved by a sequence of MILP problems, which allow us to solve large-scale MSVP problem instances faster than using MIQP solvers. We illustrate our solution schemes by solving a real MSVP problem arising in a Latin American oil and gas company. Also, we solve instances of the MSVP problem that are constructed using data from the PSPLIB library of project scheduling problems.     

考虑分时电价的多目标批调度问题蚁群算法求解

对同时优化电力成本和制造跨度的多目标批处理机调度问题进行了研究,设计了两种多目标蚁群算法,基于工件序的多目标蚁群算法(J-PACO,Job-based Pareto Ant Colony Optimization)和基于成批的多目标蚁群算法(B-PACO,Batch-based Pareto Ant Colony Optimization)对问题进行求解分析。由于分时电价中电价是时间的函数,因而在传统批调度进行批排序的基础上,需要进一步确定批加工时间点以测定电力成本。提出的两种蚁群算法分别将工件和批与时间线相结合进行调度对此类问题进行求解。通过仿真实验将两种算法对问题的求解进行了比较,仿真实验表明B-PACO算法通过结合FFLPT(First Fit Longest Processing Time)启发式算法先将工件成批再生成最终方案,提高了算法搜索效率,并且在衡量算法搜索非支配解数量的Q指标和衡量非支配集与Pareto边界接近程度的HV指标上,均优于J-PACO算法。     

Aircraft routing and crew pairing: Updated algorithms at Air France

Aircraft routing and crew pairing problems aim at building the sequences of flight legs operated respectively by airplanes and by crews of an airline. Given their impact on airlines operating costs, both have been extensively studied for decades. Our goal is to provide reliable and easy to maintain frameworks for both problems at Air France. We propose simple approaches to deal with Air France current setting. For routing, we introduce an exact compact IP formulation that can be solved to optimality by current MIP solvers in at most a few minutes even on Air France largest instances. Regarding crew pairing, we provide a methodology to model the column generation pricing subproblem within a new resource constrained shortest path framework recently introduced by the first author. This new framework, which can be used as a black-box, leverages on bounds to discard partial solutions and speed-up the resolution. The resulting approach enables to solve to optimality Air France largest instances. Recent literature has focused on integrating aircraft routing and crew pairing problems. As a side result, we are able to solve to near optimality large industrial instances of the integrated problem by combining the aforementioned algorithms within a simple cut generating method.     

Multi-objective permutation flow shop scheduling problem: Literature review,classification and current trends

The flow shop scheduling problem is finding a sequence given n jobs with same order at m machines according to certain performance measure(s). The job can be processed on at most one machine; meanwhile one machine can process at most one job. The most common objective for this problem is makespan. However, many real-world scheduling problems are multi-objective by nature. Over the years there have been several approaches used to deal with the multi-objective flow shop scheduling problems (MOFSP). Hence, in this study, we provide a brief literature review of the contributions to MOFSP and identify areas of opportunity for future research.     

Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem which has been extensively studied. Scheduling with testing is an online variant, where the processing time of a job is revealed by an extra test operation, otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing; among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3.1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take one unit of time each. We propose to first sort the jobs into non-increasing order of the minimum value between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves better competitive ratios, which approach 2.9513 when the number of machines tends to infinity in the general case; when all test operations each takes one time unit, our algorithm achieves even better competitive ratios approaching 2.8081.

     

Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach

In today's fast-paced Just-In-Time and mass customization manufacturing in a sequence-dependent setup environment, the challenge of making production schedules to meet due-date requirements is becoming a more complex problem. Unfortunately, much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. This paper considers the problem of minimizing tardiness, a common measure of due-date performance, in a sequence-dependent setup environment. Simulated annealing was used to solve the sequencing problem, and its performance was compared with random search. Our experimental results show that the algorithm can find a good solution fairly quickly, and thus can rework schedules frequently to react to variations in the schedule. The algorithm is invaluable for ‘on-line’ production scheduling and ‘last-minute’ changes to production schedule. The results of this research also suggest ways in which more complex and realistic job shop environments, such as multiple machines with a higher number of jobs in the sequence, and other scheduling objectives can be modeled. This research also investigates computational aspects of simulated annealing in solving complex scheduling problems.     

Sustainable storage assignment and dwell-point policies for automated storage and retrieval systems

Picking time reduction has been the traditional perspective for warehouse optimisation. When sustainability is considered, optimisation of warehouse operations should be read in terms of energy efficiency other than response time. Each location in the rack of an automated storage and retrieval system is associated with the value of energy consumed by the crane to reach it. Since picking performance strictly depends on storage location assignments, the time-based full turnover strategy is compared to the energy-based one. Three models of energy consumption are considered for traditional and new-generation cranes. Assignments are then compared in terms of dedicated zone shapes, time and energy performances within a given time horizon. Different shapes of the rack and product ABC curves are analysed. Dwell-point policies are also analysed from the new sustainable perspective, adding energy-saving performance to the traditional picking time reduction.     

Scheduling aerial resource operations for the extinction of large-scale wildfires

The significant increase in large-scale wildfire events in recent decades, caused primarily by climate change, has resulted in a growing number of aerial resources being used in suppression efforts. Present-day management lacks efficient and scalable algorithms for complex aerial resource allocation and scheduling for the extinction of such fires, which is crucial to ensuring safety while maximizing the efficiency of operations. In this work, we present a Mixed Integer Linear Programming (MILP) optimization model tailored to large-scale wildfires for the daily scheduling of aerial operations. The main objective is to achieve a prioritized target water flow over all areas of operation and all time periods. Minimal target completion across individual areas and time periods and total water output are also maximized as secondary and ternary objectives, respectively. An efficient and scalable multi-start heuristic, combining a randomized greedy approach with simulated annealing employing large neighborhood search techniques, is proposed for larger instances. A diverse set of problem instances is generated with varying sizes and extinction strategies to test the approaches. Results indicate that the heuristic can achieve (near)-optimal solutions for smaller instances solvable by the MILP, and gives solutions approaching target water flows for larger problem sizes. The algorithm is parallelizable and has been shown to give promising results in a small number of iterations, making it applicable for both night-before planning and, more time-sensitive, early-morning scheduling.     

Processing in a multi-machine batch manufacturing system with sequence dependent cost

Many workcells in batch manufacturing systems are populated with multiple, nonidentical machines that perform similar tasks. Because of the size of a batch when a job arrives, it may be uneconomical to set up two or more machines to process the same job simultaneously. An economic decision has to be made as regards which machine in the cell to assign the job. Likewise, many multi-operation jobs can be processed using one of several feasible operation sequences that may lead to different total manufacturing costs. The cost differences are the result of several factors, among which are processing time and cost dependencies between operations, fixturing requirements, and material handling requirements. When the workcell machine selection decision is considered along with the operation sequencing decision, determination of the best machine in a cell and the best operation sequence for the batch is a non-trivial task. In this paper, we address the problem of selecting the best machine within a cell and the best operation sequence for a batch when operation cost is machine and sequence dependent. The problem is modeled mathematically and solved using a heuristic algorithm. The performance of the algorithm is compared with that of an exact solution procedure.