Total completion time with makespan constraint in no-wait flowshops with setup times

The m-machine no-wait flowshop scheduling problem with the objective of minimizing total completion time subject to the constraint that the makespan value is not greater than a certain value is addressed in this paper. Setup times are considered non-zero values, and thus, setup times are treated as separate from processing times. Several recent algorithms, an insertion algorithm, two genetic algorithms, three simulated annealing algorithms, two cloud theory-based simulated annealing algorithms, and a differential evolution algorithm are adapted and proposed for the problem. An extensive computational analysis has been conducted for the evaluation of the proposed algorithms. The computational analysis indicates that one of the nine proposed algorithms, one of the simulated annealing algorithms (ISA-2), performs much better than the others under the same computational time. Moreover, the analysis indicates that the algorithm ISA-2 performs significantly better than the earlier existing best algorithm. Specifically, the best performing algorithm, ISA-2, proposed in this paper reduces the error of the existing best algorithm in the literature by at least 90% under the same computational time. All the results have been statistically tested.     

Performance of scheduling algorithms for no-wait flowshops with parallel machines

We study the performance of scheduling algorithms for a manufacturing system, called the ‘no-wait flowshop’, which consists of a certain number of machine centers. Each center has one or more identical parallel machines. Each job is processed by at most one machine in each center. The problem of finding the minimum finish time schedule is considered here in a flowshop consisting of two machine centers. Heuristic algorithms are presented and are analyzed in the worst case performance context. For the case of two centers, one with a single machine and the other with m, two heuristics are presented with tight performance guarantees of 3 − (1/m) and 2. When both centers have m machines, a heuristic is presented with an upper bound performance guarantee of . It is also shown that this bound can be reduced to 2(1 + ε). For the flowshop with any number of machines in each center, we provide a heuristic algorithm with an upper bound performance guarantee that depends on the relative number of machines in the centers.     

Scheduling lots of dependent unit-time operations on identical machines to minimize schedule length

Schedule of lots of unit-time operations on identical parallel machines to minimize maximum completion time is presented. The operations are subject to the precedence relation in the form of an arbitrary acyclic digraph with two integer-valued functions defined on its nodes and arcs. The problems is shown to be well solved. A theorem is proved, which provides a formula for the minimum completion time and a polynomial level-algorithm is presented. Solution results are included for a numerical example.     

Single-job lot streaming in m − 1 two-stage hybrid flowshops

This paper studies the single-job lot streaming problem in a two-stage hybrid flowshop that has m identical machines at the first stage and one machine at the second stage, to minimise the makespan. A setup time is considered before processing each sublot on a machine. For the problem with the number of sublots given, we prove that it is optimal to use a rotation method for allocating and sequencing the sublots on the machines. With such allocation and sequencing, the sublot sizes are then optimised using linear programming. We then consider the problem with equal sublot sizes and develop an efficient solution to determining the optimal number of sublots. Finally optimal and heuristic solution methods for the general problem are proposed and the worst-case performance of the equal-sublot solution is analysed. Computational results are also reported demonstrating the close-to-optimal performances of the heuristic methods in different problem settings.     

An FPTAS for scheduling with resource constraints

We study a basic scheduling problem with resource constraints: A number of jobs need to be scheduled on two parallel identical machines with the objective of minimizing the makespan, subject to the constraint that jobs may require a unit of one of the given renewable resources during their execution. For this NP-hard problem, we develop a fully polynomial-time approximation scheme (FPTAS). Our FPTAS makes a novel use of existing algorithms for the subset-sum problem and the open shop scheduling problem.     

Scheduling a hybrid assembly-differentiation flowshop to minimize total flow time

This study considers a hybrid assembly-differentiation flowshop scheduling problem (HADFSP), in which there are three production stages, including components manufacturing, assembly, and differentiation. All the components of a job are processed on different machines at the first stage. Subsequently, they are assembled together on a common single machine at the second stage. At the third stage, each job of a particular type is processed on a dedicated machine. The objective is to find a job schedule to minimize total flow time (TFT). At first, a mixed integer programming (MIP) model is formulated and then some properties of the optimal solution are presented. Since the NP-hardness of the problem, two fast heuristics (SPT-based heuristic and NEH-based heuristic) and three hybrid meta-heuristics (HGA-VNS, HDDE-VNS and HEDA-VNS) are developed for solving medium- and large-size problems. In order to evaluate the performances of the proposed algorithms, a lower bound for the HADFSP with TFT criteria (HADFSP-TFT) is established. The MIP model and the proposed algorithms are compared on randomly generated problems. Computational results show the effectiveness of the MIP model and the proposed algorithms. The computational analysis indicates that, in average, the HDDE-VNS performs better and more robustly than the other two meta-heuristics, whereas the NEH heuristic consume little time and could reach reasonable solutions.     

Scheduling subject to nonrenewable-resource constraints

Polynomially bounded solution methods are presented to solve a class of precedence constrained scheduling problems in which each job requires a certain amount of nonrenewable resource that is being consumed during its execution.     

Scheduling uniform parallel machines subject to a secondary resource to minimize the number of tardy jobs

This research investigates the problem of scheduling jobs on a set of parallel machines where the speed of the machines depends on the allocation of a secondary resource. The secondary resource is fixed in quantity and is to be allocated to the machines at the start of the schedule. The scheduling objective is to minimize the number of tardy jobs. Two versions of the problem are analyzed. The first version assumes that the jobs are pre-assigned to the machines, while the second one takes into consideration the task of assigning jobs to the machines. The paper proposes an Integer Programming formulation to solve the first case and a set of heuristics for the second.     

Scheduling: Agreement graph vs resource constraints

We investigate two scheduling problems. The first is scheduling with agreements (SWA) that consists in scheduling a set of jobs non-preemptively on identical machines in a minimum time, subject to constraints that only some specific jobs can be scheduled concurrently. These constraints are represented by an agreement graph. We extend the NP-hardness of SWA with three distinct values of processing times to only two values and this definitely closes the complexity status of SWA on two machines with two fixed processing times. The second problem is the so-called resource-constrained scheduling. We prove that SWA is polynomially equivalent to a special case of the resource-constrained scheduling and deduce new complexity results of the latter.     

A genetic algorithm for the resource constrained multi-project scheduling problem

This paper presents a genetic algorithm for the resource constrained multi-project scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a heuristic that builds parameterized active schedules based on priorities, delay times, and release dates defined by the genetic algorithm. The approach is tested on a set of randomly generated problems. The computational results validate the effectiveness of the proposed algorithm.     

Scheduling project networks with resource constraints and time windows

Project networks with time windows are generalizations of the well-known CPM and MPM networks that allow for the introduction of arbitrary minimal and maximal time lags between the starting and completion times of any pair of activities.We consider the problem to schedule such networks subject to arbitrary (even time dependent) resource constraints in order to minimize an arbitrary regular performance measure (i.e. a non-decreasing function of the vector of completion times). This problem arises in many standard industrial construction or production processes and is therefore particularly suited as a background model in general purpose decision support systems.The treatment is done by a structural approach that involves a generalization of both the disjunctive graph method in job shop scheduling [1] and the order theoretic methods for precedence constrained scheduling [18,23,24]. Besides theoretical insights into the problem structure, this approach also leads to rather powerful branch-and-bound algorithms. Computational experience with this algorithm is reported.     

On a discrete-time model with replicator dynamics in renewable resource exploitation

We consider a discrete-time version of the model proposed by Lamantia and Radi [15 F. Lamantia, and D. Radi, Exploitation of renewable resources with differentiated technologies: an evolutionary analysis, Math. Comput. Simulation 108 (2015), pp. 155–174. doi:10.1016/j.matcom.2013.09.013.[Crossref], [Web of Science ®] , [Google Scholar]] to describe a fishery where a population regulated by a logistic growth function is exploited by a pool of agents that can choose, at each time period, between two different harvesting strategies according to a profit-driven evolutionary selection rule. The resulting discrete dynamical system, represented by a two-dimensional nonlinear map, is characterized by the presence of invariant lines on which the dynamics are governed by one-dimensional restrictions that represent pure, i.e. adopted by all players, strategies. However, interesting dynamics related to interior attractors, where players playing both strategies coexist, are evidenced by analytical as well as numerical methods that reveal local and global bifurcations.     

Performance analysis of a constrained resource sharing system

We consider a queueing system where the servers are arranged in a circle, and each arriving customer requires a pair of resources that is shared by its server with the respective neighbors on either side. If either resource is being used, the customer is denied service. Customers arrive at each server according to independent Poisson processes, and lengths of service times at each server have an exponential distribution. We derive a closed-form formula for the expected fraction of busy servers at any time in terms of the number of servers and the utilization factor (defined as the arrival rate times the mean service-time duration). This allows us to evaluate system performance when these parameters are varied, and to determine whether denying service to arrivals at alternate servers improves performance. We relate the system to Dijkstra's dining philosophers problem, which is an abstraction for resource sharing in an operating system. This revised version was published online in June 2006 with corrections to the Cover Date.     

基于多Agent系统的项目调度研究

近年来 ,大型项目特别是大型工程项目存在如下的发展趋势 :1 )项目规模越来越大 ;2 )项目的复杂程度不断增加 ;3 )项目必须由多方合作才能完成 .本文针对上述特点 ,提出了基于多 Agent系统 (MAS:Multi-Agent Systems)解决资源约束条件下的项目调度问题 (RCPSP:Resource Constrained ProjectScheduling Problems)的方法 ,并通过实例项目对所提出的算法进行了验证 .     

The structure of optimal solutions for harvesting a renewable resource

We consider the problem of optimal harvesting of a renewable resource whose dynamics are governed by logistic growth and whose payoff is proportional to the harvest. We consider both the case of a finite and an infinite time horizon and analyse the structure of the optimal solutions and their dependence on the parameters of the model. We show that the optimal policy can only have one of three structures: (1) maximal harvesting effort until the resource is depleted, (2) zero harvesting during an initial time interval followed by a subsequent switch to maximal harvesting effort, or (3) a singular solution, which corresponds to an intermediate level of harvesting, accompanied by the most rapid approach path. All three scenarios emerge, with minor variations, with finite and infinite time horizons, depending on the particular combination of parameters of the system. We characterize the conditions under which the singular solution is optimal and present suggestions for designing an optimal and sustainable harvesting strategy. Recommendations for Resource Managers :

• We have rigorously explored a standard optimal harvesting model and its steady states.
• We show that three different types of solutions may emerge: (i) maximal harvesting eventually leading to a complete depletion of the stock; (ii) maximal harvesting with a potential period of idleness leading to a positive stock; (iii) an initial phase of either no or full harvesting followed by a period of intermediate harvesting intensity leading to a positive stock (singular solution).
• With some modifications, similar results hold for a finite planning horizon.
• Which of these three scenarios emerges in the finite horizon case depends not only on the parameter values but also on the length of the planning horizon.

     

Scheduling elective surgery under uncertainty and downstream capacity constraints

The objective of this study is to generate an optimal surgery schedule of elective surgery patients with uncertain surgery operations, which includes uncertainty in surgery durations and the availability of downstream resources such as surgical intensive care unit (SICU) over multi-periods. The stochastic optimization is adapted and the sample average approximation (SAA) method is proposed for obtaining an optimal surgery schedule with respect to minimizing the total cost of patient costs and overtime costs. A computational experiment is presented to evaluate the performance of the proposed method.     

具有凸资源约束的单机指数学习效应问题

研究在所有工件的正常加工时间均相同的情况下具有指数学习效应和凸资源约束的单机排序问题.给出了两种模型:在资源消耗总费用有限的情况下,以工件的最大完工时间为目标函数;在工件的最大完工时间有限的情况下,以资源消耗总费用为目标函数.求两种模型下的最优排序和最优资源分配,使得目标函数最小.证明这两个问题都是多项式时间可解的,并给出了相应的算法.     

A note on the total completion time problem in a permutation flowshop with a learning effect

The concept of learning process plays a key role in production environments. However, it is relatively unexplored in the flowshop setting. In this short note, we consider a permutation flowshop scheduling problem with a learning effect where the objective is to minimize the sum of completion times or flowtime. A dominance rule and several lower bounds are established to speed up the search for the optimal solution. In addition, the performances of several well-known heuristics are evaluated when the learning effect is present.     

Scheduling in supply chain environment

Successful companies are those that reach at least the two following objectives: reduce their Work-In-Process (WIP) and respond to customer’s requirements in real time. The approach proposed in this paper allows to reach these goals by controlling the WIP and providing information about the completion times of customer’s demands in real time. The approach we develop in this paper has been integrated in a supply chain environment for flow-shops. This paper extends the approach to assembly systems.     

A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process

One of the largest bottlenecks in iron and steel production is the steelmaking-continuous casting (SCC) process, which consists of steel-making, refining and continuous casting. The SCC scheduling is a complex hybrid flowshop (HFS) scheduling problem with the following features: job grouping and precedence constraints, no idle time within the same group of jobs and setup time constraints on the casters. This paper first models the scheduling problem as a mixed-integer programming (MIP) problem with the objective of minimizing the total weighted earliness/tardiness penalties and job waiting. Next, a Lagrangian relaxation (LR) approach relaxing the machine capacity constraints is presented to solve the MIP problem, which decomposes the relaxed problem into two tractable subproblems by separating the continuous variables from the integer ones. Additionally, two methods, i.e., the boundedness detection method and time horizon method, are explored to handle the unboundedness of the decomposed subproblems in iterations. Furthermore, an improved subgradient level algorithm with global convergence is developed to solve the Lagrangian dual (LD) problem. The computational results and comparisons demonstrate that the proposed LR approach outperforms the conventional LR approaches in terms of solution quality, with a significantly shorter running time being observed.