Abstract: Abstract
In this paper, we study online algorithms that schedule malleable jobs, i.e., jobs that can be parallelized on any subset of the available
\(m\)
identical machines. We study a model that accounts for the tradeoff between multiprocessor speedup and overhead time, namely, if job
\(j\)
has processing requirement
\(p_j\)
and is assigned to run on
\(k_j\)
machines, then
\(j\)
’s execution time becomes
\(p_j/k_j + (k_j -1)c\)
, where
\(c\)
is a constant parameter to the problem. For
\(m=2\)
, we present an online algorithm OCS that has a strong competitive ratio of 3/2, matching a previously established lower bound. We also present an online algorithm ASYM2 that is asymptotically
\(((4-\epsilon )/(3-\epsilon ))\)
-competitive when
\(m=2\)
, where
\(0 < \epsilon \le 2\)
is a parameter to the algorithm, improving upon an existing asymptotically (3/2)-competitive algorithm. Finally, we present an online algorithm OTO that is strongly
\(2\)
-competitive when
\(m = 3\)
, improving upon the previous best upper bound of
\(9/4\)
. PubDate: 2015-08-01

Abstract: Abstract
We introduce and analyze the interval shop scheduling problem, where the objective is to maximize the weighted number of jobs that can be processed in a two-stage flow shop, job shop, or open shop, where each job has a fixed start and end time and requires a given transportation time, i.e., a time lag, for moving from one stage to the other. This problem is a natural extension of the parallel-machine scheduling problem with fixed start and end times, which is relatively well understood. We prove that the two-machine interval flow shop problem is
\(\mathcal{NP }\)
-hard in the strong sense for general time lags, even in the case of equal processing times and equal weights. The problem is solvable in polynomial time if all time lags are equal. The two-machine interval job shop problem is solvable in
\(O(n^3)\)
time if the time lags are equal and relatively small. For the two-machine interval open shop problem, this is true as well. PubDate: 2015-08-01

Abstract: Abstract
Westside High School (WHS) of Omaha, Nebraska utilizes a sophisticated scheduling environment called “modular scheduling.” Modular scheduling empowers teachers with the ability to design the structure of their classes by adjusting the frequency, duration, and location of each of their lessons. This paper presents a novel heuristic methodology, implemented as a computer program called the sequential modular algorithmic routines for timetabling (SMART) Scheduler, which creates cohesive modular class schedules using effective techniques such as ejection trees and student sectioning. In experimentation, the SMART Scheduler is able to schedule over 2,800 distinct lessons in less than 4 s using data provided by WHS. This paper describes algorithms within the SMART Scheduler as well as computational results of its implementation. PubDate: 2015-08-01

Abstract: Abstract
There are a variety of joint job production and transportation scheduling problems that arise in modern manufacturing systems. In this paper, we study two such problems that arise in a flowshop environment where there are two processing stages and a single transporter that is available to deliver the finished jobs from the first stage to the second. In the first problem, there is a single machine in each of the two flowshop stages and jobs have different sizes when loaded onto the transporter. In the second problem, there are two parallel machines in the first stage and a single machine in the second stage, and the transporter can carry only one job in each shipment. The objective of both problems is to minimize the makespan, i.e., the completion time of the last job in the second stage. The two problems are both strongly NP-hard. For each problem, we propose a fast heuristic and show that the heuristic has a tight worst-case bound of 2. PubDate: 2015-08-01

Abstract: Abstract
We study a scheduling problem, in which jobs of two agents are performed in agent specific batches on the same serial unbounded batching machine. On this machine, jobs of the same batch complete simultaneously, and the batch processing time is equal to the total processing time of its jobs plus a setup time. Each agent aims at minimizing a function which depends only on the completion times of its jobs. The problem is to find a schedule that minimizes the objective function of one agent, subject to the objective function of the other agent does not exceed a given threshold. The problem appears in optimizing product consolidation operations of a cross-docking distribution center. Polynomial and pseudo-polynomial dynamic programming algorithms are derived for settings with various combinations of the objective functions. PubDate: 2015-08-01

Abstract: Abstract
In this paper we propose an efficient offline job scheduling algorithm working in a grid environment that is based on a relatively new evolutionary metaheuristic called generalized extremal optimization (GEO). We compare our experimental results with those obtained using a very popular evolutionary metaheuristic, the genetic algorithm (GA). The scheduling algorithm implies two-stage scheduling. In the first stage, the algorithm allocates jobs to suitable machines of a grid; GEO/GA is used for this purpose. In the second stage, jobs are independently scheduled on each machine; this is performed with a variant of a list scheduling algorithm. Both GEO and GA belong to the class of evolutionary algorithms, but GEO is much simpler and requires the tuning of only one parameter, whereas GA requires the tuning of several parameters. The results of the experimental study show that GEO, despite its simplicity, outperforms the GA in a whole range of scheduling instances and is much easier to use. PubDate: 2015-08-01

Abstract: Abstract
This paper deals with the problem of scheduling
\(n_\mathrm{A}\)
malleable and
\(n_\mathrm{B}\)
non-malleable jobs to be executed together on two parallel identical machines to minimize mean flow time. We propose a set of dominant schedules for this problem, and a dynamic programming algorithm that finds an optimal schedule in this dominant set in time
\(O(n_\mathrm{A}^2n_\mathrm{B})\)
. PubDate: 2015-08-01

Abstract: Abstract
Recently, the XHSTT format for high school timetabling was introduced. It provides a uniform way of modeling problem instances and corresponding solutions. The format supports a wide variety of constraints, and currently 38 real-life instances from 11 different countries are available. Thereby, the XHSTT format serves as a common ground for researchers within this area. This paper describes the first exact method capable of handling an arbitrary instance of the XHSTT format. The method is based on a mixed-integer linear programming (MIP) model, which is solved in two steps with a commercial general-purpose MIP solver. Computational results show that our approach is able to find previously unknown optimal solutions for 2 instances of XHSTT and proves optimality of 4 known solutions. For the instances not solved to optimality, new non-trivial lower bounds were found in 11 cases, and new best known solutions were found in 9 cases. Furthermore, the approach is compared with the finalists of Round 2 of the International Timetabling Competition 2011 and is shown to be competitive with one of the finalists. PubDate: 2015-08-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-06-24

Abstract: Abstract
We address one of the external factors of personnel inventory behavior, deployments. The configuration of persistent unit deployments has the ability to affect everything from individual perceptions of service palatability to operational effectiveness. There is little evidence to suggest any analytical underpinnings to the U.S. Army deployment scheduling and unit assignment patterns. This paper shows that the deployment scheduling and unit assignment problem can be formulated as an interval graph such that modifications to traditional graph coloring algorithms provide an efficient mechanism for dealing with multiple objectives. PubDate: 2015-06-10

Abstract: We study a number of variants of an abstract scheduling problem inspired by the scheduling of reclaimers in the stockyard of a coal export terminal. We analyze the complexity of each of the variants, providing complexity proofs for some and polynomial algorithms for others. For one, especially interesting variant, we also develop a constant factor approximation algorithm. PubDate: 2015-06-10

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-06-03

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-06-02

Abstract: Abstract
We revisit the batched bin packing problem. In this model, items come in K consecutive batches, and the items of the earlier batches must be packed without any knowledge of later batches. We give the first approximation algorithm for the case
\(K=2\)
, with tight asymptotic approximation ratio of 1.5833, while the known lower bound of the model is 1.378. With the application of this result, we are also able to provide an improved algorithm for the recently defined graph-bin packing problem in a special case, where we improve the upper bound from 3 to 2.5833. PubDate: 2015-06-02

Abstract: Abstract
This paper considers scheduling problems on two machines to minimise the makespan. It shows that a simple cyclical search can find a flow shop schedule with one job omitted with makespan less than or equal to the maximum of the total processing time of all jobs on either machine. This flow shop schedule is used as the basis for constructing a number of schedules with minimum makespan for the two machine open shop. The search may be applied unchanged to batches of jobs to provide more optimal schedules. PubDate: 2015-06-01

Abstract: Abstract
In the paper “The complexity of mean flow time scheduling problems with release times”, by Baptiste, Brucker, Chrobak, Dürr, Kravchenko and Sourd, the authors claimed to prove strong
\({\mathbb {NP}}\)
-hardness of the scheduling problem
\(P {\textit{pmtn}},r_j \sum C_j\)
, namely multiprocessor preemptive scheduling where the objective is to minimize the mean flow time. We point out a serious error in their proof and give a new proof of strong
\({\mathbb {NP}}\)
-hardness for this problem. PubDate: 2015-06-01

Abstract: Abstract
Makespan minimization on a set of parallel machines is one of the most widely studied problems in scheduling theory. A new result is presented which improves on the classical Coffman–Sethi a posteriori bound on the relative error of the LPT algorithm. It is shown that the ratio of these two bounds (the old one to the new one) can be arbitrarily large. PubDate: 2015-02-11