Search

This paper considers scheduling in a two-machine flow shop to maximize the total early work subject to a common due date. The early work of a job is a parameter defined as the total amount of the job that is processed before the specified due date. We mainly focus on the unweighted model in this paper, and propose a dynamic programming approach running in O ( n 2 d 2 ) time (compared with the previous result in O ( n 2 d 4 ) time for the weighted case discussed in the literature). Then we analyse the problem from an approximation point of view, in which we first show that Johnson’s algorithm, one of the most classical ones in flow shop scheduling, can only achieve the worst performance ratio for the considered problem (although it is an optimal one for makespan minimization). With the motivation of proposing better approximation algorithms, we further design a fully polynomial time approximation scheme (FPTAS). Finally, we point out that the approximation results also work for the weighted model - if a specific constraint is satisfied.

We study server scheduling on parallel dedicated machines to minimize the makespan subject to given processing sequences. Before a job starts its processing on its designated machine, a loading ope...

Recently, finding solutions to assembly flowshop scheduling problems is a topic of extensive discussion in research communities. While existing research assumes that job processing times are consta...

Purpose TED (Technology, Entertainment, Design, www.ted.com/) Talks has been one of the most popular video systems. However, the current TED Talks system expressed its inquired videos as in a two-dimensional (2D) table, which is inconvenient for searching the relationships among videos and tags. This study converts the TED Talks table into a sphere by using optimization techniques to help users search for preferred videos. Design/methodology/approach There are five phases in this study as follows. Phase 1: Reorganize data of 36 tags and 108 videos; Phase 2: Allocate tags on the TED sphere; Phase 3: Allocate videos on the TED sphere; Phase 4: Develop an online interactive TED retrieval system; and Phase 5: Perform survey and evaluation. Findings One survey demonstrated that the TED Talks sphere is more convenient for searching videos, as it is more user-friendly because of its graphical user interface, more convenient to use, more useful for retrieving information and can facilitate a more responsive search for users’ preferred videos. Research limitations/implications The numbers of tags and videos able to be displayed on a sphere is limited by the capacity of an optimization software and hardware. Practical implications The proposed sphere system can be used by a large number of users of TED Talks groups. Social implications This sphere systems can also be applied to other fields which use 2D forms to display the relationships among objects. Originality/value This study uses an optimization method to convert a 2D form into a 3D sphere to highlight the relationships among numerous objects.

In project management, especially of software development, human resource allocation is critical not only for project success including timely delivery and products quality but also for cost estimation to a software company to decide to contract projects or not. Many approaches have been proposed to provide assistance for human resource allocation in view of minimizing project duration and project cost or maximizing revenue and efficiency. These approaches may sometimes not be comprehensive in real-world environments without addressing some key factors like transferring cost, communication, and negative efficiency, which usually have crucial impacts on assignment applicability. This article is proposing a framework for assisting a software company to evaluate existing resource for making decisions on whether the estimation of the tender is feasible, and assisting to make human resource allocation for team formation in fixed project duration with labor skill and budget constraint. Within consideration of both the cost and the efficiency, the performance is maximized to verges on the customers’ expectations in software development project management on the basis of a real case. Before forming a team for a specific project with well-defined periods and numbers of people with different project roles, the values of key factors in the framework are calculated with individual foundation of computation. We formulate the decision process in integer programming models, and a simulation study is conducted to demonstrate the applicability of the proposed model to assist the decision making process of software companies for team formation. The results of four variants for maximum skill efficiency or minimum hiring cost are illustrated with different considerations of both key factors are included or not proposed in this paper, and demonstrate that these factors could bring out different sources to help companies in making further evaluations for allocating staff in a software development project.

We address a two-machine no-wait flowshop scheduling problem with respect to the performance measure of total completion time. Minimizing total completion time is important when inventory cost is of concern. Setup times are treated separately from processing times. Furthermore, setup times are uncertain with unknown distributions and are within some lower and upper bounds. We develop a dominance relation and propose eight algorithms to solve the problem. The proposed algorithms, which assign different weights to the processing and setup times on both machines, convert the two-machine problem into a single-machine one for which an optimal solution is known. We conduct computational experiments to evaluate the proposed algorithms. Computational experiments reveal that one of the proposed algorithms, which assigns the same weight to setup and processing times, is superior to the rest of the algorithms. The results are statistically verified by constructing confidence intervals and test of hypothesis.

Bi-criteria lexicographical minimization problems with the makespan as the primary objective and the total machine assignment costs as the secondary objective have been recently introduced to the scheduling research, and polynomial time ( r + 1 , 1 ) -approximation algorithms have been suggested for their solution, where 1 r 2 is the performance ratio of an approximation algorithm for P | | C max . We improve these results by presenting a polynomial time ( 1.5 r − 1 , 1 ) -approximation algorithm for the additive cost type. Then, we introduce a problem of minimizing the total machine assignment cost over the Δ-approximate solutions of the makespan minimization problem. We prove that this new problem is strongly NP-hard and pseudo-polynomially non-approximable in general. A polynomial time approximation algorithm with a guaranteed approximation ratio is presented for the additive cost type and bounded ratio between the maximal and minimal machine costs. An O ( m n 2 k ) time dynamic programming algorithm is also presented, where k is the fixed number of distinct job processing times.

This paper considers scheduling of surgical operations across multiple operating rooms subject to the limited availability of anaesthetists. The objective is to construct a feasible operations schedule that has the minimum makespan, i.e., the completion time of all operations. We abstract the problem into a theoretical server scheduling problem and formulate it in a mathematical form by proposing an integer programming model. Due to the intractability of its computing time, we circumvent the exact approaches and develop two approximation methods. Then, the steepest descent search is adopted for improving the solutions. Computational study suggests that the proposed methods can produce quality solutions in a few seconds.

This paper investigates a variant of parallel-machine scheduling problems with conflict constraints. A set of identical parallel machines is available for processing a set of jobs subject to conflict constraints, which specify pairs of jobs that are mutually disjoint due to resource availability. Jobs conflicting to each other cannot be processed simultaneously. The scheduling problem is to construct a feasible schedule that optimizes the considered managerial performance measures. This paper discusses the specific two-machine setting where each machine has a designated set of jobs to process. We give NP-hardness proofs for the case with the presence of a fixed processing sequence on one of the machines. Polynomial-time dynamic programming algorithms are proposed to produce optimal schedules for the case where the processing sequences on both machines are known and fixed a priori.

This study considers the manufacturing environments in which m + 1 machines are configured as two-stage flexible flow shops with dedicated machines (F2DM). The F2DM scheduling problems arise naturally from practical production and fabrication systems, and they are classified into two categories, whose machine settings are antithetical to each other. In model 1, a single common bottleneck machine is installed at stage 1 and m parallel dedicated machines comprise stage 2. The second model has the m dedicated machines at stage 1 and the bottleneck machine at stage 2. Categorizing the literature according to the performance metrics, we survey the existing research results of the two models and propose several new solution procedures with improved computational complexity. The complexity results are summarized, and suggestions are made for future research.

This paper investigates the classical preemptive parallel-machine scheduling problem of maximizing number of on-time jobs. While the problem is known to be NP-hard, no theoretical analysis of approximation algorithms exists in the literature. As part of the analysis, a new non-standard mixed integer formulation is developed. We propose heuristics based on different design strategies. These heuristics have asymptotically tight relative errors of 1/2. Experimental tests evaluate the computational performance of the procedures.

We consider parallel-machine scheduling with a common server and job preemption to minimize the makespan. While the non-preemptive version of the problem is strongly NP-hard, the complexity status of the preemptive version has remained open. We show that the preemptive version is NP-hard even if there is a fixed number of machines. We give a pseudo-polynomial time algorithm to solve the case with two machines. We show that the case with an arbitrary number of machines is unary NP-hard, analyze the performance ratios of some natural heuristic algorithms, and present several solvable special cases.© 2017 Wiley Periodicals, Inc. Naval Research Logistics, 2017

The celebrated Johnson’s algorithm to solve the two-machine flowshop scheduling problem to minimise the makespan plays a prominent role in scheduling research. In using resource-constrained scheduling to interpret Johnson’s algorithm in teaching scheduling theory and operations management, we have received positive student feedback on the perceived intuition. We demonstrate this idea and show that the resource-constrained scheduling concept also helps simplify the proofs of some classical scheduling results.

This paper proposes a dynamic programming algorithm for the NRCSRP with multiple crews. This algorithm also improves the existing algorithm for the problem with a single crew.

This paper proposes a production scheduling procedure for the production lines of a printed circuit board company. Linearity features of the manufacturing process of this company are characterized and exploited for developing an efficient three-phase scheduling procedure. The production line is formulated as a linear job shop that resembles a flow shop. First, the N-gram modelling approach is adopted to analyse the data sets to detect the machines that would be candidates of the bottleneck in the production lines. Second, according to the candidates, the bottleneck data are extracted from the original data sets and solved as flow shops by a mixed integer programming model. The optimal solutions of the bottleneck flow shop is next extended by incorporating upstream and down stream operations to form approximate solutions of the original problems. We propose three different strategies for forming the approximate solutions and the best one is designated as the final solution. The performance of the proposed heuristic algorithm is tested and compared with the well-known NEH algorithm through numerical instances from real production lines. Statistics indicate that for most instances including up to 80 jobs the proposed method delivers competitive solutions within a much shorter time than the NEH algorithm.

This paper investigates the talent scheduling problem in film production, which is known as rehearsal scheduling in music and dance performances. The first lower bound on the minimization of talent hold cost is based upon the outside-in branching strategy. We introduce two approaches to add extra terms for tightening the lower bound. The first approach is to formulate a maximum weighted matching problem. The second approach is to retrieve structural information and solve a maximum weighted 3-grouping problem. We make two contributions: First, our results can fathom the matrix of a given partial schedule. Second, our second approach is free from the requirement to schedule some shooting days in advance for providing anchoring information as in the other approaches, i.e., a lower bound can be computed once the input instance is given. The lower bound can fit different branching strategies. Moreover, the second contribution provides a state-of-the-art research result for this problem. Computational experiments confirm that the new bounds are much tighter than the original one.

Cloud computing has been attracting considerable attention since the last decade. This study considers a decision problem formulated from the use of computing services over the Internet. An agent receives orders of computing tasks from his/her clients and on the other hand he/she acquires computing resources from computing service providers to fulfill the requirements of the clients. The processors are bundled as packages according to their speeds and the business strategies of the providers. The packages are rated at a certain pricing scheme to provide flexible purchasing options to the agent. The decision of the agent is to select the packages which can be acquired from the service providers and then schedule the tasks of the clients onto the processors of the acquired packages such that the total cost, including acquisition cost and scheduling cost (total weighted tardiness), is minimized. In this study, we present an integer programming model to formulate the problem and propose several solution methods to produce acquisition and scheduling plans. Ten well-known heuristics of parallel-machine scheduling are adapted to fit into the studied problem so as to provide initial solutions. Tabu search and genetic algorithm are tailored to reflect the problem nature for improving upon the initial solutions. We conduct a series of computational experiments to evaluate the effectiveness and efficiency of all the proposed algorithms. The results of the numerical experiments reveal that the proposed tabu search and genetic algorithm can attain significant improvements. HighlightsAn acquisition planning model of computing resource is introduced.The model incorporates scheduling decisions.Several solution approaches are proposed.Performances of the approaches are examined through computational experiments.

One of the commercial Internet applications is banner advertisement, which is also the major source of income for portal websites. Limited research works address the issues of efficiently scheduling advertisement requests into available advertisement banners in view of profitably. This paper proposes a new model for scheduling banner advertisements that more closely resembles the Internet business world. In the proposed model, we apply a feasible time window to each candidate order, and schedule advertisements into various predefined banner spaces on the webpage. This approach allows different pricing strategies according to banner types and is contrary to previous research models that schedule and price by banner space sharing. Each order for ad space will demand a certain frequency for each type of banner. The goal is to select and schedule requests to achieve the maximum ad capacity utilization. We first give a mathematical formulation to formally describe the problem. Due to the computational complexity of the studied problem, we seek to produce approximate solutions in a reasonable time. A three-phase heuristic is developed to cope with this problem. In addition, an upper bound on profits is developed. Computational experiments are designed to examine the performance of the heuristic. Statistics from the experiments reveal that the heuristic can successfully fill up to 97% of ad spaces.

This paper studies the problem of scheduling three-operation jobs in a two-machine flowshop subject to a predetermined job processing sequence. Each job has two preassigned operations, which are to be performed on their respective dedicated machines, and a flexible operation, which may be processed on either of the two machines subject to the processing order as specified. Five standard objective functions, including the makespan, the maximum lateness, the total weighted completion time, the total weighted tardiness, and the weighted number of tardy jobs are considered. We show that the studied problem for either of the five considered objective functions is ordinary NP-hard, even if the processing times of the preassigned operations are zero for all jobs. A pseudo-polynomial time dynamic programming framework, coupled with brief numerical experiments, is then developed for all the addressed performance metrics with different run times.

This paper investigates the scheduling problem in a two-stage flexible flow shop, which consists of m stage-1 parallel dedicated machines and a stage-2 bottleneck machine, subject to the condition that n l jobs per type l∈{1, …, m} are processed in a fixed sequence. Four regular performance metrics, including the total completion time, the maximum lateness, the total tardiness, and the number of tardy jobs, are considered. For each considered objective function, we aim to determine an optimal interleaving processing sequence of all jobs coupled with their starting times on the stage-2 bottleneck machine. The problem under study is proved to be strongly NP-hard. An O(m 2Π l=1 m n l 2) dynamic programming algorithm coupled with numerical experiments is presented.

A new variant of resource-constrained scheduling problem is introduced.The concept of optional operations is proposed.Complexity status of the problem is discussed. This paper introduces a scheduling problem with a variant of resource constraint that stems from a relocation project. We also propose the concept of optional recycling operations, in which recycling operations are separated from the processing of jobs and recycling operations are exercised only when necessary. An integer program is proposed to formulate the problem and facilitate complexity classification. We propose a pseudo-polynomial time dynamic program, and then classify the complexity status of several restricted cases.

In a two-machine flow shop, the problem seeks to select and schedule jobs such that the processing of the selected jobs does not contain any idle time. The objective is to maximize the number of selected jobs. The problem is studied in the context of a resource-constrained scheduling problem. An $$O(n^2)$$ dynamic programming algorithm is proposed. The problem becomes ordinary NP-hard when job weights are introduced. A heuristic is designed and its performance ratio is analysed to be 3.

This paper investigates a single-machine scheduling problem with a set of supporting tasks and a set of jobs. Each job is preceded by a subset of supporting tasks, that is, the job cannot start its processing until all of its supporting tasks are finished. The objective functions are defined solely in job completion times. We discuss the complexities of several special cases for the number of late jobs and the total weighted completion time. This study adds new complexity results to the two standard objective functions under precedence constraints.

We consider parallel machine scheduling problems where the processing of the jobs on the machines involves two types of objectives. The first type is one of two classical objective functions in scheduling theory: either the total completion time or the makespan. The second type involves an actual cost associated with the processing of a specific job on a given machine; each job-machine combination may have a different cost. Two bi-criteria scheduling problems are considered: (1) minimize the maximum machine cost subject to the total completion time being at its minimum, and (2) minimize the total machine cost subject to the makespan being at its minimum. Since both problems are strongly NP-hard, we propose fast heuristics and establish their worst-case performance bounds.

This study is concerned with the manufacturing model that has a common machine at stage one and two parallel dedicated machines at stage two. All jobs need to be processed on the stage-one common machine. After the stage-one processing, the jobs of type 1 (type 2) will route to the first (second) dedicated machine at stage two. We first elaborate several published works on makespan minimisation which are not known to other streams of recent works. While the minimisation of maximum lateness is strongly NP-hard, we develop a linear-time algorithm to solve the case where two sequences of the two job types are given a priori.

The recent work of Chen et al. (2018) elaborates on the lower bound of Lin, Lin, and Lee (2006) concerning total late work minimization in two-machine flow-shop scheduling, denoted by F2||∑Yi or F2...

This paper studies a problem of scheduling fabrication and assembly operations in a two-machine flowshop, subject to the same predetermined job sequence on each machine. In the manufacturing setting, there are n products, each of which consists of two components: a common component and a unique component which are fabricated on machine 1 and then assembled on machine 2. Common components of all products are processed in batches preceded by a constant setup time. The manufacturing process related to each single product is called a job. We address four regular performance measures: the total job completion time, the maximum job lateness, the total job tardiness, and the number of tardy jobs. Several optimality properties are presented. Based upon the concept of critical path and block schedule, a generic dynamic programming algorithm is developed to find an optimal schedule in O(n7) time. © 2014 Springer Science+Business Media New York.

This article considers a differentiation flow-shop model, where the jobs are divided into various categories, each of which consists of two stages of operations. All products should be processed first on the single common machine at stage 1. At the second stage, each individual product proceeds to a dedicated machine according to its type. The problem of makespan minimization under the setting with two product types is known to be strongly NP hard. This article considers an arbitrary number of job types by developing a lower bound and two dominance rules, based upon which branch-and-bound algorithms are designed. Computational experiments are carried out to examine the performance of the proposed properties. The statistics show that the proposed properties can substantially reduce the computing efforts required for finding optimal solutions.

We propose from the perspective of operations scheduling a novel model of the refurbishing process in recycling management. We model the refurbishing process as a two-stage flowshop that dismantles products into parts in stage one and refurbishes the parts on dedicated machines in stage two. The model also features that the performance measure of a schedule is defined by operation-based completion times, which is different from the job-based performance measures traditionally adopted in the scheduling literature. We analyse the optimality properties and computational complexity of some special cases of the problem. We derive lower bounds on the optimal solution based on a disaggregation technique and the assignment problem, and develop dominance rules incorporating estimates of the effects of partial schedules on unscheduled jobs. We present a heuristic approach, based on LP relaxation, and analyse its performance ratio. We also develop two metaheuristic algorithms, based on iterated local search ...

This paper studies a sequence-dependent scheduling problem incorporating order delivery, motivated by satellite imaging scheduling. A set of jobs is to be processed on a single machine and each job belongs to a specific group. The completion time of a group is the moment when all jobs belonging to this group are completed. The problem is to determine a processing sequence of the jobs such that the sum of weighted completion times over all groups is minimized. We present a binary integer program to formulate the studied problem and then develop an O(n^22^n) dynamic programming algorithm for determining optimal solutions. To produce approximate solutions within an acceptable time, we design a tabu search algorithm, an iterated local search algorithm and a genetic algorithm. Computational experiments are conducted to study the performance of the integer program and the solution algorithms. Numerical statistics suggest that the binary integer program can reach optimal solutions faster than the integer program existing in the literature, and the iterated local search algorithm outperforms other approaches when the number of jobs increases.

This paper considers a two-stage three-machine differentiation flow shop that comprises a common machine at stage 1 and two independent dedicated machines at stage 2. Two types of jobs are to be processed. All jobs must visit the stage-1 machine, and then the jobs of each type proceed to their dedicated machine for stage-2 processing. The stage-1 machine processes the jobs in batches, each of which, whenever formed, requires a constant setup time. The objective is to find a schedule that attains the minimum makespan. While the problem is strongly NP-hard, we investigate the case where the processing sequences of the two types of jobs are given and fixed. A polynomial-time dynamic programming algorithm is designed to solve this problem. We then deploy this algorithm to compute the lower bounds of the general problem.

This study investigates sequence optimization of media objects in a multimedia presentation that is dynamically composed from digital libraries. Each media object can be associated with a due date. The aim is to schedule the media objects in a delay-prone network environment such that the overall presentation lag and the due date penalties of the media objects of presentations can be minimized. We formulate the sequencing problem with buffer constraints in the media player into a flowshop scheduling problem and present a reduction strategy with a branch and bound algorithm to derive optimal sequences. The algorithm can be applied in applications with up to a dozen objects to be scheduled. In addition, we propose a modified NEH-based heuristic algorithm which can provide approximate solutions with an average error rate of less than 4%. The computation-efficient heuristic, when deployed in applications with heavily loaded servers, can obtain near-optimal sequences for problems with more than a dozen objects. The proposed algorithms are embedded into a prototype system for providing digital library services.

This paper studies a two-machine flow shop scheduling problem with a supporting precedence relation. The model originates from a real production context of a chemical factory that produces foam-rubber products. We extend the traditional two-machine flow shop by dividing the operations into two categories: supporting tasks and regular jobs. In the model, several different compositions of foam rubber can be mixed at the foam blooming stage, and products are processed at the manufacturing stage. Each job (product) on the second machine cannot start until its supporting tasks (parts) on the first machine are all finished and the second machine is not occupied. The objective is to find a schedule that minimizes the total job completion time. The studied problem is strongly NP-hard. In this paper, we propose a branch-and-bound algorithm incorporating a lower bound and two dominance rules. We also design a simple heuristic and an iterated local search (ILS) algorithm to derive approximate solutions. The performances of the proposed algorithms are examined through computational experiments.

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.

Materials acquisition is one of the critical challenges faced by academic libraries. This paper presents an integer programming model of the studied problem by considering how to select materials in order to maximize the average preference and the budget execution rate under some practical restrictions including departmental budget, limitation of the number of materials in each category and each language. To tackle the constrained problem, we propose a discrete particle swarm optimization (DPSO) with scout particles, where each particle, represented as a binary matrix, corresponds to a candidate solution to the problem. An initialization algorithm and a penalty function are designed to cope with the constraints, and the scout particles are employed to enhance the exploration within the solution space. To demonstrate the effectiveness and efficiency of the proposed DPSO, a series of computational experiments are designed and conducted. The results are statistically analyzed, and it is evinced that the proposed DPSO is an effective approach for the studied problem.

© 2015, Springer Science+Business Media New York. This study addresses a relocation scheduling problem that corresponds to resource-constrained scheduling on two parallel dedicated machines where the processing sequences of jobs assigned to the machines are given and fixed. Subject to the resource constraints, the problem is to determine the starting times of all jobs for each of the six considered regular performance measures, namely, the makespan, total weighted completion time, maximum lateness, total weighted tardiness, weighted number of tardy jobs, and number of tardy jobs. By virtue of the proposed dynamic programming framework, the studied problem for the minimization of makespan, total weighted completion time, or maximum lateness can be solved in (Formula presented.) time, where (Formula presented.) and (Formula presented.) are the numbers of jobs on the two machines. The simplified case with a common job processing time can be solved in (Formula presented.) time. For the objective function of total weighted tardiness or weighted number of tardy jobs, this problem is proved to be NP-hard in the ordinary sense, and the case with a common job processing length is solvable in (Formula presented.) time. The studied problem for the minimization of number of tardy jobs is solvable in (Formula presented.) time. The solvability of the common-processing-time problems can be generalized to the m-machine cases, where (Formula presented.).

This paper considers the relocation problem arising from public re-development projects cast as a two-machine flowshop scheduling problem. In such a project, some buildings need to be torn down and re-constructed. The two processes of tearing down and re-constructing each building are often viewed as a single operation. However, under certain circumstances, the re-construction process, i.e., the resource recycling process, can be viewed as a separate operation. In this paper we regard these two processes as separate on the assumption that they are handled by different working crews. We formulate the problem as a resource-constrained two-machine flowshop scheduling problem with the objective of finding a feasible re-development sequence that minimizes the makespan. We provide problem formulations, discuss the complexity results, and present polynomial algorithms for various special cases of the problem.

This paper discusses a two-stage assembly-type flowshop scheduling problem with batching considerations subject to a fixed job sequence. The two-stage assembly flowshop consists of m stage-1 parallel dedicated machines and a stage-2 assembly machine which processes the jobs in batches. Four regular performance metrics, namely, the total completion time, maximum lateness, total tardiness, and number of tardy jobs, are considered. The goal is to obtain an optimal batching decision for the predetermined job sequence at stage 2. This study presents a two-phase algorithm, which is developed by coupling a problem-transformation procedure with a dynamic program. The running time of the proposed algorithm is O(mn+n 5), where n is the number of jobs.

The paper considers makespan minimization on a single machine subject to release dates in the relocation problem, originated from a resource-constrained redevelopment project in Boston. Any job consumes a certain amount of resource from a common pool at the start of its processing and returns to the pool another amount of resource at its completion. In this sense, the type of our resource constraints extends the well-known constraints on resumable resources, where the above two amounts of resource are equal for each job. In this paper, we undertake the first complexity analysis of this problem in the case of arbitrary release dates. We develop an algorithm, based on a multi-parametric dynamic programming technique (when the number of parameters that undergo enumeration of their values in the DP-procedure can be arbitrarily large). It is shown that the algorithm runs in pseudo-polynomial time when the number m of distinct release dates is bounded by a constant. This result is shown to be tight: (1) it cannot be extended to the case when m is part of the input, since in this case the problem becomes strongly NP-hard, and (2) it cannot be strengthened up to designing a polynomial time algorithm for any constant m>1, since the problem remains NP-hard for m=2. A polynomial-time algorithm is designed for the special case where the overall contribution of each job to the resource pool is nonnegative. As a counterpart of this result, the case where the contributions of all jobs are negative is shown to be strongly NP-hard.

This paper investigates single-machine coupled-task scheduling where each job has two tasks separated by an exact delay. The objective of this study is to schedule the tasks to minimize the makespan subject to a given job sequence. We introduce several intriguing properties of the fixed-job-sequence problem under study. While the complexity status of the studied problem remains open, an O(n^2) algorithm is proposed to construct a feasible schedule attaining the minimum makespan for a given permutation of 2n tasks abiding by the fixed-job-sequence constraint. We investigate several polynomially solvable cases of the fixed-job-sequence problem and present a complexity graph of the problem.

Since optical WDM networks are becoming one of the alternatives for building up backbones, dynamic routing, and wavelength assignment with delay constraints (DRWA-DC) in WDM networks with sparse wavelength conversions is important for a communication model to route requests subject to delay bounds. Since the NP-hard minimum Steiner tree problem can be reduced to the DRWA-DC problem, it is very unlikely to derive optimal solutions in a reasonable time for the DRWA-DC problem. In this paper, we circumvent to apply a meta-heuristic based upon the ant colony optimization (ACO) approach to produce approximate solutions in a timely manner. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. The ACO algorithm proposed in this paper incorporates several new features so as to select wavelength links for which the communication cost and the transmission delay of routing the request can be minimized as much as possible subject to the specified delay bound. Computational experiments are designed and conducted to study the performance of the proposed algorithm. Comparing with the optimal solutions found by an ILP formulation, numerical results evince that the ACO algorithm is effective and robust in providing quality approximate solutions to the DRWA-DC problem.