Single machine scheduling with batch deliveries

The single machine batch scheduling problem is studied. The jobs in a batch are delivered to the customer together upon the completion time of the last job in the batch. The earliness of a job is defined as the difference between the delivery time of the batch to which it belongs and its completion time. The objective is to minimize the sum of the batch delivery and job earliness penalties. A relation between this problem and the parallel machine scheduling problem is identified. This enables the establishment of complexity results and algorithms for the former problem based on known results for the latter problem.     

On the machine scheduling problem with job delivery coordination

This paper examines two scheduling problems with job delivery coordination, in which each job demands different amount of storage space during transportation. For the first problem, in which jobs are processed on a single machine and delivered by one vehicle to a customer, we present a best possible approximation algorithm with a worst-case ratio arbitrarily close to 3/2. For the second problem, which differs from the first problem in that jobs are processed by two parallel machines, we give an improved algorithm with a worst-case ratio 5/3.     

订单带多工类工件时的极小迟后范围问题

本文考虑下述由多工类工件组成的订单的单机排序问题：每一个客户提供一个由若干工件组成的订单,总共n个工件又分成k个类．当机器从加工某类中的工件转向加工不同于它的第i类工件时,需一调整时间si．每一订单有一给定的应交工时间,订单的完工时间定义为该定单所含全部工件完工时的时间．我们希望适当排列这n个工件,使得订单的迟后范围最小．相应这一排序问题,文中依不同的背景给出了以下二种模式：同类工件一起连续加工,工件的完工时间为其所属类中全部工件完工时的时间,用GT,Ba来表示；同类工件一起连续加工,工件的完工时间为其本身的完工时间,用GT,Ja来表示．对于这两种模式的排序同题,我们均证明了其NP-hard性并给出了对应的分枝定界算法．     

Minimizing the Range of Order Completion Times with Multiple Job Classes

A number of important contributions have been made toward the problem of minimizing the difference in ‘customer’ treatment on a single machine. However, so far, all the research has been to solve the problem of minimizing the ‘job’ difference. That is, it is assumed implicitly that each customer places only one job, and hence minimizing the difference in customer treatment is equivalent to minimizing the difference in job treatment. In many practical situations, a customer may place an order which consists of several jobs. The jobs usually can be grouped into different classes. Thus, the range, i.e. the difference between the maximum and the minimum, of order completion times becomes an appropriate performance measure for treating customers equally. In this paper, a dynamic programming (DP) algorithm is developed to provide the optimal solution. Due to the exponential time complexity of the DP algorithm, two heuristic methods are also proposed to solve large-sized problems. Computational results for the heuristics are provided.     

带有机器维修和两车辆派送的单机排序问题

研究了带有机器维修和工件派送的单机排序问题,该问题可以被视为一个集成生产和出站配送的排序模型。不同体积的工件需要在带有一个维修区间的机器上加工,且加工不可中断,然后由固定容量的两辆同类车批次交付给单客户,目标函数是极小化最大完工时间,本文提出了2-近似算法,并证明了2是紧界。     

具有多个不可用时间段的单机供应链排序问题

在单机供应链排序问题中, 机器会有多个长度确定的不可用时间段,它仅可以在可用时间段内加工工件,且每个可用时间段的长度不大于给定的常数.多个完工工件可组成一批由一个容量无限制的运输工具发送给客户.问题的目标是如何 安排工件的加工、发送以及不可用时间段,以使总发送时间与总发送费用之和达到最小. 对于工件加工可恢复的情况,可在多项式时间 O(n^2) 内得到最优序. 对于工件加工不可恢复的情况,证明了问题是强NP-难的, 并提出了~2-近似算法.     

订单带多类工件时的最大迟后问题

本文考虑多工类工件的单机排序问题,每一客户提供一由若干工件组成的订单,总共n个工件又分成k个类,当机器从加工某类中的工件转向加工不同于它的第i类工件时需一调整时间S_i,每一订单有一给定的应交工时间,所考虑目标函数是使订单的最大迟后最小,相应这一排序问题的三种模式,文中分别给出了一多项式算法,分枝定界算法和动态规划解法。     

Flexible job shop scheduling with overlapping in operations

In this paper, flexible job shop scheduling problem with a new approach, overlapping in operations, is discussed. In many flexible job shops, a customer demand can be released more than one for each job, where demand determines the quantity of each finished job ordered by a customer. In these models each job has a demand more than one. This assumption is an important and practical issue for many flexible job shops such as petrochemical industries. To consider this assumption, we use a new approach, named overlapping in operations. In this approach, embedded operations of each job can be performed due to overlap considerations in which each operation may be overlapped with the others because of its nature. The overlapping is limited by structural constraints, such as the dimensions of the box to be packed or the capacity of the container used to move the pieces from one machine to the next. Since this problem is well known as NP-Hard class, a hierarchical approach used simulated annealing algorithm is developed to solve large problem instances. Moreover, a mixed integer linear programming (MILP) method is presented. To evaluate the validity of the proposed SA algorithm, the results are compared with the optimal solution obtained with the traditional optimization technique (The Branch and Bound method). The computational results validate the efficiency and effectiveness of the proposed algorithm. Also the computational results show that the overlapping considering can improve the makespan and machines utilization measures. So the proposed algorithm can be applied easily in real factory conditions and for the large size problems and it should thus be useful to both practitioners and researchers.     

Metaheuristics for the multi-objective FJSP with sequence-dependent set-up times,auxiliary resources and machine down time

This paper investigates the application of particle swarm optimization (PSO) to the multi-objective flexible job shop scheduling problem with sequence-dependent set-up times, auxiliary resources and machine down time. To achieve this goal, alternative particle representations and problem mapping mechanisms were implemented within the PSO paradigm. This resulted in the development of four PSO-based heuristics. Benchmarking on real customer data indicated that using the priority-based representation resulted in a significant performance improvement over the existing rule-based algorithms commonly used to solve this problem. Additional investigation into algorithm scalability led to the development of a priority-based differential evolution algorithm. Apart from the academic significance of the paper, the benefit of an improved production schedule can be generalized to include cost reduction, customer satisfaction, improved profitability, and overall competitive advantage.     

A hybrid two-stage transportation and batch scheduling problem

We study the coordinated scheduling problem of hybrid batch production on a single batching machine and two-stage transportation connecting the production, where there is a crane available in the first-stage transportation that transports jobs from the warehouse to the machine and there is a vehicle available in the second-stage transportation to deliver jobs from the machine to the customer. As the job to be carried out is big and heavy in the steel industry, it is reasonable assumed that both the crane and the vehicle have unit capacity. The batching machine processes a batch of jobs simultaneously. Each batch occur a setup cost. The objective is to minimize the sum of the makespan and the total setup cost. We prove that this problem is strongly NP-hard. A polynomial time algorithm is proposed for a case where the job transportation times are identical on the crane or the vehicle. An efficient heuristic algorithm for the general problem is constructed and its tight worst-case bound is analyzed. In order to further verify the performance of the proposed heuristics, we develop a lower bound on the optimal objective function. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances.     

具有两种运输方式选择的物流排序问题

本文研究了单机环境下,有两种运输方式可供选择的集成生产和运输的排序问题。有多个工件需要在一台机器上进行加工,工件生产完后需要分批运到客户处。有两种运输方式,普通运输和特快运输可供选择。制造商需要安排工件的加工顺序,选择合适的运输方式和出发时间,以极小化相应的时间目标与运输费用的加权和。研究了排序理论中主要的两个目标函数,分析了问题的复杂性,对于这些问题给出了它们的最优算法。     

储存时间有上限的两阶段供应链排序问题

研究一类储存时间有上限的两阶段供应链排序问题.两阶段是指工件先加工,后运输:加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件.工件的运输完成时刻与完工时刻之差定义为工件的储存时间,且有相应的储存费用,且任意工件的储存时间都不超过某一常数.若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻,则有相应的提前(延误)惩罚费用.目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和.先证明该问题是NP-难的,后对单位时间的储存费用不超过单位时间的延误惩罚费用的情形给出了伪多项式时间算法.     

加工时间和尺寸成正比单机排序和工件运输的最小化最大完工时间问题

在单机排序和工件运输的最小化最大完工时间问题中,工件首先在一台机器上加工,然后被一辆有容量限制的汽车运送到一个顾客．当工件的加工时间和尺寸无关时, Chang和Lee已经证明该问题是强NP困难的．他们也给出了一个启发式算法,它的最差执行比为5／3,并且这个界是紧的．本文考虑工件的加工时间和尺寸成正比的情形,证明了Chang和Lee的算法有更好的最差执行比53／35,并提供了一个新的启发式算法,它的最差执行比是3／2,并且这个界是最好的．     

Column generation heuristics for multiple machine, multiple orders per job scheduling problems

Front opening unified pods (FOUPs) are used to store and transport silicon wafers in 300-mm semiconductor wafer fabs. To achieve production efficiencies, wafers are grouped together in FOUPs without regard to the originating customer placing the order. In the resulting multiple orders per job (moj) scheduling problem, scheduling is performed at the FOUP (i.e., aggregated order) level, while scheduling performance is assessed per individual customer order. Column generation heuristics are presented for single and parallel machine moj scheduling problems to minimize total weighted order completion time. The proposed heuristics obtain near-optimal solutions very quickly, outperforming competing approaches in the literature.     

Approximation algorithm for minimizing total latency in machine scheduling with deliveries

We study the problem of minimizing total latency in machine scheduling with deliveries, which is defined as follows. There is a set of n jobs to be processed by a single machine at a plant, where job J_i is associated with its processing time and a customer i located at location i to which the job is to be delivered. In addition, there is a single uncapacitated delivery vehicle available. All jobs (vehicle) are available for processing (delivery) at time 0. Our aim is to determine the sequence in which the jobs should be processed in the plant, the departure times of the vehicle from the plant, and the routing of the vehicle, so as to minimize the total latency (job delivery time). We present a 6e16.309691-approximation algorithm for the problem.     

优化交货期窗口的两阶段供应链排序问题

研究一类优化交货期窗口的两阶段供应链排序问题. 优化交货期窗口是指交货期窗口的开始与结束时刻是决策变量, 不是输入常量. 两阶段是指工件先加工, 后运输: 加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件. 工件的开始运输时刻与完工时刻之差定义为工件的储存时间, 且有相应的储存费用. 若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻, 则有相应的提前(延误)惩罚费用. 目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和. 针对单位时间的延误惩罚费用不超过单位时间的储存费用、单位时间的储存费用不超过单位时间的提前惩罚费用的情形, 给出了时间复杂性为O(n^{8})的动态规划算法.     

Bi-criteria group scheduling with sequence-dependent setup time in a flow shop

A bi-criteria group scheduling problem in a flow shop with sequence-dependent setup time is investigated in this paper. Manufacturing cell and flow shop are two popular scenarios in industry. Dynamic job releases and machine availabilities are assumed. The goal is to minimize the weighted sum of total weighted completion time and total weighted tardiness, which are aimed at satisfying the producer and customer goals separately. Normalized weights are assigned to both criteria to describe the trade-off between the two objectives. Two different initial solution finding mechanisms are proposed, and a tabu-search-based two-level search algorithm is deve1loped to find optimal/near-optimal solutions for the problem. A mathematical model is also developed and implemented to evaluate the optimality of the results from search algorithms for small problem instances. To further uncover the difference in performance of initial solutions and algorithms, an experimental design is performed and results are reported.     

Fuzzy scheduling of job orders in a two-stage flowshop with batch-processing machines

In this paper, we present a mixed-integer fuzzy programming model and a genetic algorithm (GA) based solution approach to a scheduling problem of customer orders in a mass customizing furniture industry. Independent job orders are grouped into multiple classes based on similarity in style so that the required number of setups is minimized. The family of jobs can be partitioned into batches, where each batch consists of a set of consecutively processed jobs from the same class. If a batch is assigned to one of available parallel machines, a setup is required at the beginning of the first job in that batch. A schedule defines the way how the batches are created from the independent jobs and specifies the processing order of the batches and that of the jobs within the batches. A machine can only process one job at a time, and cannot perform any processing while undergoing a setup. The proposed formulation minimizes the total weighted flowtime while fulfilling due date requirements. The imprecision associated with estimation of setup and processing times are represented by fuzzy sets.     

加工时间可控和简单线性增长的平行机排序

本文研究加工时间可控并随开工时间简单线性增长的平行机排序问题.证明了该问题为NP-难问题,该问题存在满足以下性质的最优排序:每个工件的加工时间要么完全压缩,要么完全不压缩;每台机器的工件排序由一个工件参数和控制变量的函数的递增序给出.通过将问题等价转换为0-1非线性整数规划问题,给出了平行机排序问题的贪婪算法.     

Machine scheduling with a maintenance interval and job delivery coordination

We investigate a scheduling problem with job delivery coordination in which the machine has a maintenance time interval. The goal is to minimize the makespan. In the problem, each job needs to be processed on the machine non-preemptively for a certain time, and then transported to a distribution center, by one vehicle with a limited physical capacity. We present a 2-approximation algorithm for the problem, and show that the performance ratio is tight.