Abstract: Abstract
The Joint Replenishment Problem (
\({\hbox {JRP}}\)
) is a fundamental optimization problem in supply-chain management, concerned with optimizing the flow of goods from a supplier to retailers. Over time, in response to demands at the retailers, the supplier ships orders, via a warehouse, to the retailers. The objective is to schedule these orders to minimize the sum of ordering costs and retailers’ waiting costs. We study the approximability of
\({\hbox {JRP-D}}\)
, the version of
\({\hbox {JRP}}\)
with deadlines, where instead of waiting costs the retailers impose strict deadlines. We study the integrality gap of the standard linear-program (LP) relaxation, giving a lower bound of
\(1.207\)
, a stronger, computer-assisted lower bound of
\(1.245\)
, as well as an upper bound and approximation ratio of
\(1.574\)
. The best previous upper bound and approximation ratio was
\(1.667\)
; no lower bound was previously published. For the special case when all demand periods are of equal length, we give an upper bound of
\(1.5\)
, a lower bound of
\(1.2\)
, and show APX-hardness. PubDate: 2015-12-01

Abstract: Abstract
Coupled tasks are two-operation tasks, where the two operations are separated by a time interval of fixed duration. Coupled task scheduling problems refer then to the scheduling of a set of coupled tasks on a single machine. Applications of these problems, reported in the literature, arise in connection with radar systems, robotic cells, and in manufacturing. Most of the complexity issues for scheduling coupled tasks have been settled. However, the complexity status has been unknown for the identical coupled task problem, where multiple copies of a single coupled task are to be processed. The purpose of the article is to solve this open problem in the cyclic case, for which we prove the polynomial complexity. PubDate: 2015-12-01

Abstract: Abstract
The resource-constrained project scheduling problem with minimum and maximum time lags (RCPSP/max) is a general model for resource scheduling in many real-world problems (such as manufacturing and construction engineering). We consider RCPSP/max problems where the durations of activities are stochastic and resources can have unforeseen breakdowns. Given a level of allowable risk,
\(\alpha \)
, our mechanisms aim to compute the minimum robust makespan execution strategy. Robust makespan for an execution strategy is any makespan value that has a risk less than
\(\alpha \)
. The risk for a makespan value,
\(M\)
given an execution strategy, is the probability that a schedule instantiated from the execution strategy will not finish before
\(M\)
given the uncertainty over durations and resources. We make three key contributions: (a) firstly, we provide an analytical evaluation of resource breakdowns and repairs on executions of activities; (b) we then incorporate such information into a local search framework and generate execution strategies that can absorb resource and durational uncertainties; and (c) finally, to improve robustness of resulting strategies, we propose resource breakdown aware chaining procedure with three different metrics. This chaining procedure computes resource allocations by predicting the effect of breakdowns on robustness of generated strategies. Experiments show effectiveness of our proposed methods in providing more robust execution strategies under uncertainty. PubDate: 2015-12-01

Abstract: Abstract
Consider the following scheduling problem. We are given a set of jobs, each having a release time, a due date, a processing time, and demand for machine capacity. The goal is to schedule all jobs non-preemptively in their release-time deadline windows on machines that can process multiple jobs simultaneously, subject to machine capacity constraints, with the objective to minimize the total busy time of the machines. Our problem naturally arises in power-aware scheduling, optical network design, and customer service systems, among others. The problem is APX-hard by a simple reduction from the subset sum problem. A main result of this paper is a 5-approximation algorithm for general instances. While the algorithm is simple, its analysis involves a non-trivial charging scheme which bounds the total busy time in terms of work and span lower bounds on the optimum. This improves and extends the results of Flammini et al. (Theor Comput Sci 411(40–42):3553–3562, 2010). We extend this approximation to the case of moldable jobs, where the algorithm also needs to choose, for each job, one of several processing-time versus demand configurations. Better bounds and exact algorithms are derived for several special cases, including proper interval graphs, intervals forming a clique and laminar families of intervals. PubDate: 2015-12-01

Abstract: Abstract
We consider the problem of scheduling a set of jobs on a single machine subject to inventory constraints, i.e., conditions that jobs add or remove items to or from a centralized inventory, respectively. Jobs that remove items cannot be processed if the required number of items is not available. We focus on scheduling problems on a single machine where the objective is to minimize the total weighted completion time. In this paper, we design 2-approximation algorithms for special cases of the problem that run in polynomial time. PubDate: 2015-12-01

Abstract: Abstract
In this paper, we study a robust single-machine scheduling problem under four alternative optimization criteria: minimizing total completion time, minimizing total weighted completion time, minimizing maximum lateness, and minimizing the number of late jobs. We assume that job processing times are subject to uncertainty. Accordingly, we construct three alternative uncertainty sets, each of which defines job processing times that can simultaneously occur. The robust optimization framework assumes that, given a job schedule, a worst-case set of processing times will be realized from among those allowed by the uncertainty set under consideration. For each combination of objective function and uncertainty set, we first analyze the problem of identifying a set of worst-case processing times with respect to a fixed schedule, and then investigate the problem of selecting a schedule whose worst-case objective is minimal. PubDate: 2015-12-01

Abstract: Abstract
Many supply chains use returnable packaging such as plastic and metal containers, folding boxes, racks, and trays to transport components from suppliers to buyers. This study investigates the scheduling problem of a supplier that produces jobs for several buyers where the jobs for each buyer have to be delivered in that buyer’s returnable containers. Empty containers are provided by the buyers at certain release dates. The supplier can process a job when no adequate empty containers are available, but then incurs extra handling costs to pack the job into auxiliary packaging and repack it later. This study extends single machine scheduling with weighted earliness and tardiness penalties and batching by including returnable containers and repacking penalties. A mathematical programming formulation and a two-stage heuristic for this previously unstudied NP-hard scheduling problem are proposed and evaluated in a numerical study. PubDate: 2015-12-01

Abstract: Abstract
We consider a semi-online multiprocessor scheduling problem with a given a set of identical machines and a sequence of jobs, the sum of whose processing times is known in advance. The jobs are to be assigned online to one of the machines and the objective is to minimize the makespan. The best known algorithm for this problem achieves a competitive ratio 1.6 (Cheng et al. in Theor Comput Sci 337:134–146, 2005). The best known lower bound is approximately 1.585 (Albers and Hellwig in Theor Comput Sci 443:1–9, 2012) if the number of machines tends to infinity. We present an elementary algorithm with competitive ratio equal to this lower bound. Thus, the algorithm is best possible if the number of machines tends to infinity. PubDate: 2015-12-01

Abstract: Abstract
This paper addresses a recent open scheduling problem which aims to minimize the summation of total weighted completion time and the total machine time slot cost. Focusing on the case of non-increasing time slot cost with non-preemptive jobs, we show that the problem can be solved in polynomial-time when the time slot cost decreases with certain patterns, including linearly decreasing, decreasing concave, and decreasing convex cases. Different methodologies are used for three cases. For the linearly decreasing case, we can classify all the jobs into three categories and schedule the job sets one by one. For the decreasing concave case, we calculate each job’s worst starting time and try to make them far away from their worst starting times. For the decreasing concave case, we calculate each job’s best starting time and let them start close to their best starting times. Finally, we show that the problem is NP-hard in the strong sense when the time slot cost decreases in an arbitrary way. PubDate: 2015-11-26

Abstract: Abstract
This paper studies a multi-agent scheduling problem on two identical parallel machines. There are g agents, and each agent’s objective is to minimize its makespan. We present an approximation algorithm such that the performance ratio of the makespan achieved by our algorithm relative to the minimum makespan is no more than
\(i+\frac{1}{6}\)
for the ith
\((i=1,2,\ldots ,g)\)
completed agent. Moreover, we show that the performance ratio is tight. PubDate: 2015-11-13

Abstract: Abstract
Many real-world situations involve queueing systems in which customers may abandon if service does not start sufficiently quickly. We study a comprehensive model of multi-class queue scheduling accounting for customer abandonment, with the objective of minimizing the total discounted or time-average sum of linear waiting costs, completion rewards, and abandonment penalties of customers in the system. We assume the service times and abandoning times are exponentially distributed. We solve analytically the case in which there is one server and there are one or two customers in the system and obtain an optimal policy. For the general case, we use the framework of restless bandits to analytically design a novel simple index rule with a natural interpretation. We show that the proposed rule achieves near-optimal or asymptotically optimal performance both in single- and multi-server cases, both in overload and underload regimes, and both in idling and non-idling systems. PubDate: 2015-11-11

Abstract: Abstract
The semiconductor manufacturing industry is significantly expensive both in equipment and materials. Cluster tools, a type of automated manufacturing system integrating processing modules and transport modules, are commonly used in this industry. Nowadays, multi-cluster tools, which are composed of several cluster tools connected by joint buffer modules, are often used for wafer production. This paper deals with K-unit cycle scheduling problems in single-armed two-cluster tools for processing identical wafers in deterministic settings. In a K-unit cycle, K wafers are exactly inserted into the two-cluster tool, and K completed wafers leave the two-cluster tool, usually not the same K wafers. Residency constraints and general moving times by the robot are both considered. The objective is to obtain optimal K-unit cycle schedules, which minimize cycle times. To analyze this scheduling problem in detail, a mixed integer linear programming (MILP) model is formulated and solved. Numerical examples are used to explain how the solution can be obtained from the MILP model in a K-unit cycle. PubDate: 2015-11-06

Abstract: Abstract
The application of the Late Acceptance Hill-Climbing (LAHC) to solve the High School Timetabling Problem is the subject of this manuscript. The original algorithm and two variants proposed here are tested jointly with other state-of-art methods to solve the instances proposed in the Third International Timetabling Competition. Following the same rules of the competition, the LAHC-based algorithms noticeably outperformed the winning methods. These results, and reports from the literature, suggest that the LAHC is a reliable method that can compete with the most employed local search algorithms. PubDate: 2015-11-06

Abstract: Abstract
It is well known that in the twentieth century, mathematical programming (MP) modeling and particularly linear programming (LP) modeling, even though strongly applied to combinatorial optimization, were not too successful when directed to scheduling problems. The purpose of this paper is to show that the field of successful applications of LP/MP modeling is still growing and includes also scheduling topics. We first focus on single machine scheduling. We consider a single machine scheduling model where a quadratic programming (QP) formulation handled by means of a QP solver is shown to be competitive with the state of the art approaches. Also, we discuss a single machine bicriterion scheduling problem and show that a standard LP formulation based on positional completion times performs reasonably well when handled by means of a LP solver. Then, we show how LP can be used to tighten bounds for approximation results in sequencing problems. Finally, we show how to enhance the complexity bounds of branch-and-reduce exact exponential algorithms by means of the so-called measure-and-conquer paradigm requiring always the solution of a specific MP model. PubDate: 2015-11-03

Abstract: Abstract
The resource leveling problem (RLP) involves the determination of a project baseline schedule that specifies the planned activity starting times while satisfying both the precedence constraints and the project deadline constraint under the objective of minimizing the variation in the resource utilization. However, uncertainty is inevitable during project execution. The baseline schedule generated by the deterministic RLP model tends to fail to achieve the desired objective when durations are uncertain. We study the robust resource leveling problem in which the activity durations are stochastic and the objective is to obtain a robust baseline schedule that minimizes the expected positive deviation of both resource utilizations and activity starting times. We present a genetic algorithm for the robust RLP. In order to demonstrate the effectiveness of our genetic algorithm, we conduct extensive computational experiments on a large number of randomly generated test instances and investigate the impact of different factors (the marginal cost of resource usage deviations, the marginal cost of activity starting time deviations, the activity duration variability, the due date, the order strength, the resource factor and the resource constrainedness). PubDate: 2015-10-16

Abstract: Abstract
This note considers the longest processing time heuristic for scheduling n independent jobs on two uniform parallel machines to minimize the makespan. A posterior worst-case performance ratio, by depending on the index of the latest job inserted in the machine where the makespan takes place, is developed for this heuristic, and some examples demonstrate that the ratio is tight. PubDate: 2015-10-12

Abstract: Abstract
Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an integer
\(k\)
, find a set of at least
\(k\)
pairwise non-adjacent vertices). Here, one encounters special graph classes like 2-union graphs (edge-wise unions of two interval graphs) and strip graphs (edge-wise unions of an interval graph and a cluster graph), on which Independent Set remains
\(\mathrm{NP}\)
-hard but admits constant ratio approximations in polynomial time. We study the parameterized complexity of Independent Set on 2-union graphs and on subclasses like strip graphs. Our investigations significantly benefit from a new structural “compactness” parameter of interval graphs and novel problem formulations using vertex-colored interval graphs. Our main contributions are as follows:
We show a complexity dichotomy: restricted to graph classes closed under induced subgraphs and disjoint unions, Independent Set is polynomial-time solvable if both input interval graphs are cluster graphs, and is
\(\mathrm{NP}\)
-hard otherwise.
We chart the possibilities and limits of effective polynomial-time preprocessing (also known as kernelization).
We extend Halldórsson and Karlsson (2006)’s fixed-parameter algorithm for Independent Set on strip graphs parameterized by the structural parameter “maximum number of live jobs” to show that the problem (also known as Job Interval Selection) is fixed-parameter tractable with respect to the parameter
\(k\)
and generalize their algorithm from strip graphs to 2-union graphs. Preliminary experiments with random data indicate that Job Interval Selection with up to 15 jobs and
\(5\cdot 10^5\)
intervals can be solved optimally in less than 5 min. PubDate: 2015-10-01

Abstract: Abstract
Subcontracting allows manufacturer agents to reduce completion times of their jobs and thus obtain savings. This paper addresses the coordination of decentralized scheduling systems with a single subcontractor and several agents having divisible jobs. Assuming complete information, we design parametric pricing schemes that strongly coordinate this decentralized system, i.e., the agents’ choices of subcontracting intervals always result in efficient schedules. The subcontractor’s revenue under the pricing schemes depends on a single parameter which can be chosen to make the revenue as close to the total savings as required. Also, we give a lower bound on the subcontractor’s revenue for any coordinating pricing scheme. Allowing private information about processing times, we prove that the pivotal mechanism is coordinating, i.e., agents are better off by reporting their true processing times, and by participating in the subcontracting. We show that the subcontractor’s maximum revenue with any coordinating mechanism under private information equals the lower bound of that with coordinating pricing schemes under complete information. Finally, we address the asymmetric case where agents obtain savings at different rates per unit reduction in completion times. We show that coordinating pricing schemes do not always exist in this case. PubDate: 2015-10-01

Abstract: Abstract
In a scenario characterized by a continuous growth of air transportation demand, the runways of large airports serve hundreds of aircraft every day. Aircraft sequencing is a challenging problem that aims to increase runway capacity in order to reduce delays as well as the workload of air traffic controllers. In many cases, the air traffic controllers solve the problem using the simple “first-come-first-serve” (FCFS) rule. In this paper, we present a rolling horizon approach which partitions a sequence of aircraft into chunks and solves the aircraft sequencing problem (ASP) individually for each of these chunks. Some rules for deciding how to partition a given aircraft sequence are proposed and their effects on solution quality investigated. Moreover, two mixed integer linear programming models for the ASP are reviewed in order to formalize the problem, and a tabu search heuristic is proposed for finding solutions to the ASP in a short computation time. Finally, we develop an IRHA which, using different chunking rules, is able to find solutions significantly improving on the FCFS rule for real-world air traffic instances from Milano Linate Airport. PubDate: 2015-10-01

Abstract: We address a novel integrated maintenance and production scheduling problem in a multi-machine and multi-period production system, considering maintenance as a long-term decision. Deterioration of machines over time decreases production capacity. Since maintenance activities not only improve machine conditions, increasing production capacity, but also take time that cannot be used for production, the challenge is to assign maintenance to periods and to schedule maintenance and production activities within each period to minimize the combined cost of maintenance and lost production over the planning horizon. Motivated by logic-based Benders decomposition, we design an integrated two-stage algorithm to solve the problem. The first stage assigns maintenance to machines and time periods, abstracting the scheduling problem, while the second stage creates a schedule for the current time period. The first stage is then re-solved using feedback from the schedule. This iteration between maintenance planning and scheduling continues until the solution costs in two stages converge. The integrated approach models the interdependencies between maintenance and scheduling decisions in highly coupled processes such as wafer fabrication in the semiconductor manufacturing. Our results demonstrate that the benefit of integrated decision making increases when maintenance is less expensive relative to lost production cost and that a longer horizon for maintenance planning is beneficial when maintenance cost increases. PubDate: 2015-10-01