A memetic differential evolution algorithm for energy-efficient parallel machine scheduling

This paper considers an energy-efficient bi-objective unrelated parallel machine scheduling problem to minimize both makespan and total energy consumption. The parallel machines are speed-scaling. To solve the problem, we propose a memetic differential evolution (MDE) algorithm. Since the problem involves assigning jobs to machines and selecting an appropriate processing speed level for each job, we characterize each individual by two vectors: a job-machine assignment vector and a speed vector. To accelerate the convergence of the algorithm, only the speed vector of each individual evolves and a list scheduling heuristic is applied to derive its job-machine assignment vector based on its speed vector. To further enhance the algorithm, we propose efficient speed adjusting and job-machine swap heuristics and integrate them into the algorithm as a local search approach by an adaptive meta-Lamarckian learning strategy. Computational results reveal that the incorporation of list scheduling heuristic and local search greatly strengthens the algorithm. Computational experiments also show that the proposed MDE algorithm outperforms SPEA-II and NSGA-II significantly.     

Online scheduling on parallel machines with two GoS levels

This paper investigates the online scheduling problem on parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels. Hence each job and machine are labeled with the GoS levels, and each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine. The goal is to minimize the makespan. In this paper, we consider the problem with two GoS levels. It assumes that the GoS levels of the first k machines and the last m−k machines are 1 and 2, respectively. And every job has a GoS level of 1 alternatively or 2. We first prove the lower bound of the problem under consideration is at least 2. Then we discuss the performance of algorithm AW presented in Azar et al. (J. Algorithms 18:221–237, 1995) for the problem and show it has a tight bound of 4−1/m. Finally, we present an approximation algorithm with competitive ratio . Research supported by Natural Science Foundation of Zhejiang Province (Y605316) and its preliminary version appeared in Proceedings of AAIM2006, LNCS, 4041, 11-21.     

SOLUTION OF THE SHORTEST ROUTE PROBLEM USING THE ASSIGNMENT TECHNIQUE

A solution to the shortest route problem of going from city i to city j with p necessary intermediate stops (0 p n - 2) is given using the assignment algorithm, with a simple modification of the initial matrix. A branch and bound algorithm is necessary in all but the simplest case (p = 0).     

A heuristic approach for component scheduling on a high-speed PCB assembly machine

The collect-and-place machine is one of the most widely used placement machines for assembling electronic components on the printed circuit boards (PCBs). Nevertheless, the number of researches concerning the optimisation of the machine performance is very few. This motivates us to study the component scheduling problem for this type of machine with the objective of minimising the total assembly time. The component scheduling problem is an integration of the component sequencing problem, that is, the sequencing of component placements; and the feeder arrangement problem, that is, the assignment of component types to feeders. To solve the component scheduling problem efficiently, a hybrid genetic algorithm is developed in this paper. A numerical example is used to compare the performance of the algorithm with different component grouping approaches and different population sizes.     

The hierarchical model for load balancing on two machines

Following previous work, we consider the hierarchical load balancing model on two machines of possibly different speeds. We first focus on maximizing the minimum machine load and show that no competitive algorithm exists for this problem. We overcome this barrier in two ways, both related to previously known models. The first one is fractional assignment, where each job can be arbitrarily split between the machines. The second one is a semi-online model where the sum of jobs is known in advance. We design algorithms of best possible competitive ratios for both these cases. Furthermore, we show that the combination of the two models leads to the existence of an optimal algorithm (i.e., an algorithm of competitive ratio 1). This algorithm is clearly optimal for the makespan minimization problem as well. For the latter problem, we consider the fractional assignment model and design an algorithm of best possible competitive ratio for it. This work was submitted as the M.Sc. thesis of the first author.     

ON PREDICTING COMPUTATIONAL TIME OF A BRANCH AND BOUND ALGORITHM FOR THE ASSIGNMENT OF FACILITIES

Experience with branch and bound algorithms indicates that computational time is a function of not only the size of the problem, but also the nature of the input data. This paper formulates statistically-based variables which describe certain characteristics of the input data and experimentally evaluates their ability to predict computational time for one branch and bound algorithm, the relative location of facilities or “plant layout” problem. Results suggest that the described experimental procedure may be useful for an a priori assessment of the computational difficulty of specific branch and bound problems.     

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

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

Single facility scheduling with dual criteria: minimizing maximum tardiness subject to minimum number of tardy jobs

This paper considers the static single machine scheduling problem with the objective of minimizing the maximum tardiness of any job subject to the constraint that the total number of lardy jobs is minimum. Based on simple dominance conditions an o(n²) heuristic algorithm is proposed to find an approximate solution to this problem. The effectiveness of the proposed heuristic algorithm is empirically evaluated by solving a large number of problems and comparing them to the optimal solutions obtained through the branch and bound algorithm.     

Scheduling with machine cost and rejection

In this paper we consider the scheduling problem with machine cost and rejection penalties. For this problem, we are given a sequence of independent jobs, each being characterized by its processing time (size) and its penalty. No machine is initially provided, and when a job is revealed the algorithm has the option to purchase new machines. Right when a new job arrives, we have the following choices: (i) reject it, in which case we pay its penalty; (ii) non-preemptively process it on an existing machine, which contributes to the machine load; (iii) purchase a new machine, and assign it to this machine. The objective is to minimize the sum of the makespan, the cost for purchasing machines, and the total penalty of all rejected jobs. For the small job case, (where all jobs have sizes no greater than the cost for purchasing one machine, and which is the generalization of the Ski-Rental Problem) we present an optimal online algorithm with a competitive ratio of 2.     

Ordinal On-Line Scheduling for Maximizing the Minimum Machine Completion Time

This paper considers the on-line problem of scheduling nonpreemptively n independent jobs on m > 1 identical and parallel machines with the objective to maximize the minimum machine completion time. It is assumed that the values of the processing times are unknown but the order of the jobs by their processing times is known in advance. We are asked to decide the assignment of all the jobs to some machines at time zero by utilizing only ordinal data rather than the actual magnitudes of jobs. Algorithms to slove the problem are called ordinal algorithms. In this paper, we give lower bounds and ordinal algorithms. We first propose an algorithm MIN which is at most -competitive for any m machine case, while the lower bound is _i=1 ^m 1/i. Both are on the order of (ln m). Furthermore, for m = 3, we present an optimal algorithm.     

A BRANCH AND BOUND PROCEDURE FOR SETUP PROBLEMS IN FLEXIBLE MANUFACTURING SYSTEMS

We address a medium- to short-term production planning problem in a flexible manufacturing environment. First we present a single-machine, mixed integer programming model for part type selection and lot-sizing problems over a T-period planning horizon. Demand for part types changes dynamically through the periods. The objective is to meet the demand for part types during the periods they are demanded. Available machine time and tool magazine capacities are the system constraints in our models. We next extend on the single- machine model to include multiple machines. In addition to part type selection and lotsizing decisions, the extended model also addresses the machine-loading decision. We present exact branch and bound procedures based on linear programming relaxations for the two models. We also report the results of our computational experiments.     

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.     

O(m2) ALGORITHMS FOR THE TWO AND THREE SUBLOT LOT STREAMING PROBLEM

Lot streaming is the process of splitting a job or lot into sublots to reduce its makespan on a sequence of machines. The goal in the lot streaming problem is to find the optimal size of each sublot that will minimize the makespan. The makespan is defined as the time the last sublot completes its processing on the last machine. If the sizes of these sublots are restricted to remain the same on all machines, the solution is called a consistent sublot solution. However, if the sizes of the sublots are allowed to vary, the solution is referred to as a nonconsistent or variable sublot solution. Also, if the machines must be in operation continuously from the first to the last sublot, the solution is a no idling solution. When setups are explicitly considered in the problem, there will be two cases. If setups on each machine require some portion of the first sublot be present by the machine, the problem is referred to as the attached setup time problem. If setups can be performed ahead of time before the first sublot reaches the particular machine, the corresponding problem is referred to as the detached setup problem. Finally, if the machines are allowed to be idle between the processing of sublots, the resultant solution is an intermittent idling solution. In this paper, the consistent sublot lot streaming problem with intermittent idling and no setups is discussed. The models developed also assume that the number of sublots are fixed and known. The m machine two sublot lot streaming problem is reviewed. An algorithm for the three sublot, m machine problem is derived using a network representation of the problem. The complexity of the algorithm is O (m²). Finally, using the insights from three sublot problem, a heuristic algorithm is provided for the m machine, n sublot problems. The results on the proposed heuristic are very encouraging; average percent deviation from optimal makespan is approximately at 0.76% on 155 randomly generated problems with different m and n values.     

基于改进遗传算法的置换装配线调度问题研究

企业的置换装配线调度问题（Permutation Assembly-line Scheduling Problem,PASP）是一类典型的NP-hard型生产调度问题,是现代集成制造系统CIMS极为关心的问题。该问题可以具体描述为n个工件要在m台机器上加工,每个工件需要经过m道工序,每道工序要求不同的机器,这n个工件通过m台机器的顺序相同,它们在每台机器上的加工顺序也相同,问题的主要目标是找到n个工件在每台机器上的最优加工顺序,使得最大完工时间最小。由于PASP问题的NP-hard性质,本文使用遗传算法对其进行求解。尽管遗传算法常用以求解调度问题,但其选择与交叉机制易导致局部最优及收敛慢。因此,本文提出基于区块挖掘与重组的改进遗传算法用于求解置换装配线调度问题。首先通过关联规则挖掘出不同的优秀基因,然后将具有较优结果的基因组合为优势区块,产生具优势的人工解,并引入高收敛性的局部搜索方法,提高搜索到最优解的机会与收敛效率。本文以OR-Library中Taillard标准测试例来验证改进遗传算法的求解质量与效率,结果证明：本文所提算法与其它求解调度问题的现有5种知名算法相比,不仅收敛速度较快,同时求解质量优于它们。     

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.     

基于系统最优的城市公交专用道网络设计模型及算法

设置公交专用道是实现"公交优先"的重要手段,然而,专用道设置将改变不同交通方式的道路通行能力,进而影响交通网络的整体性能。本文试图提出一种基于系统最优思想的公交专用道网络设计方法,既保证出行者的利益,又能满足交通系统总费用最优的目标。首先,本文分析了公交专用道设置对公交车辆和社会车辆这两种交通方式道路通行能力的影响,基于经典的BPR函数,构造了考虑专用道设置的不同方式的路段阻抗函数。其次,分析了出行者在多方式交通网络中的模式选择和路径选择问题,采用用户平衡理论分析了城市多方式交通平衡配流问题,给出了相应的变分不等式模型。更进一步,采用双层规划方法构造了基于系统最优的城市公交专用道网络设计模型,该模型以交通网络总费用最小为优化目标,并考虑了不同交通方式的平衡流量约束,采用分支定界算法对该双层规划模型进行求解。最后,通过一个简单算例对模型及算法的可行性和有效性进行了分析和验证。     

Preemptive Machine Covering on Parallel Machines

This paper investigates the preemptive parallel machine scheduling to maximize the minimum machine completion time. We first show the off-line version can be solved in O(mn) time for general m-uniform-machine case. Then we study the on-line version. We show that any randomized on-line algorithm must have a competitive ratio m for m-uniform-machine case and ∑_{i = 1}^m1/i for m-identical-machine case. Lastly, we focus on two-uniform-machine case. We present an on-line deterministic algorithm whose competitive ratio matches the lower bound of the on-line problem for every machine speed ratio s≥ 1. We further consider the case that idle time is allowed to be introduced in the procedure of assigning jobs and the objective becomes to maximize the continuous period of time (starting from time zero) when both machines are busy. We present an on-line deterministic algorithm whose competitive ratio matches the lower bound of the problem for every s≥ 1. We show that randomization does not help.     

MINIMIZING TOTAL WEIGHTED COMPLETION TIME ON A SINGLE BATCH PROCESSING MACHINE

We study the problem of scheduling jobs on a single batch processing machine to minimize the total weighted completion time. A batch processing machine is one that can process a number of jobs simultaneously as a batch. The processing time of a batch is given by the processing time of the longest job in the batch. We present a branch and bound algorithm to obtain optimal solutions and develop lower bounds and dominance conditions. We also develop a number of heuristics and evaluate their performance through extensive computational experiments. Results show that two of the heuristics consistently generate high-quality solutions in modest CPU times.     

Improved algorithmic results for unsplittable stable allocation problems

The stable allocation problem is a many-to-many generalization of the well-known stable marriage problem, where we seek a bipartite assignment between, say, jobs (of varying sizes) and machines (of varying capacities) that is “stable” based on a set of underlying preference lists submitted by the jobs and machines. Building on the initial work of Dean et al. (The unsplittable stable marriage problem, 2006), we study a natural “unsplittable” variant of this problem, where each assigned job must be fully assigned to a single machine. Such unsplittable bipartite assignment problems generally tend to be NP-hard, including previously-proposed variants of the unsplittable stable allocation problem (McDermid and Manlove in J Comb Optim 19(3): 279–303, 2010). Our main result is to show that under an alternative model of stability, the unsplittable stable allocation problem becomes solvable in polynomial time; although this model is less likely to admit feasible solutions than the model proposed in McDermid and Manlove (J Comb Optim 19(3): 279–303, McDermid and Manlove 2010), we show that in the event there is no feasible solution, our approach computes a solution of minimal total congestion (overfilling of all machines collectively beyond their capacities). We also describe a technique for rounding the solution of a stable allocation problem to produce “relaxed” unsplit solutions that are only mildly infeasible, where each machine is overcongested by at most a single job.     

A METHODOLOGY FOR LABOR SCHEDULING IN A SERVICE OPERATING SYSTEM

In the increasingly competitive services sector, utilization of the labor force can make the difference between profits or losses. Until recently, service operations managers had a limited set of tools, most of them computer-based, for scheduling labor. This paper offers a manual heuristic for labor scheduling that outperforms traditional algorithmic solution approaches. Specifically, this study examines the problem of scheduling employees in service delivery system subject to demand variability. The manual heuristic proposed asigns full-time empolyees to weekly work schedules with the objective of minimizing the total number of labor hours scheduled. The performance of the manual heuristic is compared to the classical algorithmic solution and to a lower bound for a variety of demand distributions and system operating conditions. The heuristic is shown to produce a smaller work force than the classical approach in 106 of the 108 demand-operating condition patterns examined.