On-line scheduling of unit time jobs with rejection: minimizing the total completion time

We consider on-line scheduling of unit time jobs on a single machine with job-dependent penalties. The jobs arrive on-line (one by one) and can be either accepted and scheduled, or be rejected at the cost of a penalty. The objective is to minimize the total completion time of the accepted jobs plus the sum of the penalties of the rejected jobs.We give an on-line algorithm for this problem with competitive ratio . Moreover, we prove that there does not exist an on-line algorithm with competitive ratio better than 1.63784.     

Two-machine flow shop scheduling with deteriorating jobs: minimizing the weighted sum of makespan and total completion time

This paper considers a two-machine flow shop scheduling problem with deteriorating jobs in which the processing times of jobs are dependent on their starting times in the sequence. The objective is to minimize the weighted sum of makespan and total completion time. To analyse the problem, we propose a mixed integer programming model, and discuss several polynomially solvable special cases. We also present a branch-and-bound algorithm with several dominance rules, an upper bound and a lower bound. Finally, we present results of computational experiments conducted to evaluate the performance of the proposed model and the exact algorithm.     

Minimization of the maximal penalty in the case of preemption of jobs

For a class of structural sets of penalty functions={_i} _i=1 ⁿ with lower quasiconvex functions _i defined for sets of jobs={_i} _i=1 ⁿ , one gives an algorithm for solving the problem n /1/ preemp ¦ max, having order 0(np), where n is the number of jobs _i and p is the total length of the completion of all jobs of the set.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 102, pp. 61–67, 1980.In conclusion, the author expresses her gratitude to K. V. Shakhbazyan for his interest in this paper.     

On minimizing the weighted number of late jobs in unit execution time open-shops

We study unit execution time open-shops with integer release dates. This paper shows that, in this environment, the minimum weighted number of late jobs can be computed in polynomial time by dynamic programming. The complexity status of the corresponding problem Om|p_ij=1,r_i|∑w_iU_i was unknown before.     

A new branch and bound algorithm for minimizing the weighted number of tardy jobs

In this paper, the problem of sequencing jobs on a single machine to minimize the weighted number of tardy jobs is considered. Some new dominances between jobs are proposed and studied. A new branch and bound algorithm that can solve large problems, e.g. 85 jobs, is presented.     

Scheduling jobs with release dates,equal processing times,and inclusive processing set restrictions

We consider the problem of scheduling a given set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a given release date and is compatible to only a subset of the machines. The machines are ordered and indexed in such a way that a higher-indexed machine can process all the jobs that a lower-indexed machine can process. We present a solution procedure to solve this problem in O(n²+mnlogn) time. We also extend our results to the tree-hierarchical processing sets case and the uniform machine case.     

A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates

In this paper we consider the scheduling problem of minimizing the weighted number of late jobs on a single machine (1|_rj|∑_wjUj)$\left(1|r_j|\sum w_j{U}_j\right)$. A branch-and-check algorithm is proposed, where a relaxed integer programming formulation is solved by branch-and-bound and infeasible solutions are cut off using infeasibility cuts. We suggest two ways to generate cuts. First, tightened “no-good” cuts are derived using a modification of the algorithm by Carlier (1982, EJOR, v.11, 42–47) which was developed for the problem of minimizing maximum lateness on a single machine. Secondly we show how to create cuts by using constraint propagation. The proposed algorithm is implemented in the Mosel modelling and optimization language. Computational experiments on instances with up to 140 jobs are reported. A comparison is presented with the exact approach of Péridy at al. (2003, EJOR, v.148, 591–603).     

The maximization of a function over the efficient set via a penalty function approach

In this paper we present several equivalent mathematical programming formulations of the problem of maximizing a function over the efficient set, in the case of a polytopal feasible region and linear functions. Penalty function formulations and their properties are given. An examination is made of computational aspects, epsilon efficiency, the appropriateness of the original problem formulation, and of nonlinear extensions.     

Quality of move-optimal schedules for minimizing total weighted completion time

We study the minimum total weighted completion time problem on identical machines. We analyze a simple local search heuristic, moving jobs from one machine to another. The local optima can be shown to be approximately optimal with approximation ratio . In a special case, the approximation ratio is .     

The singular set of an energy minimizing map fromB 4 toS 2

The singular set of an energy minimizing map from a four dimensional domain toS ² consists locally of a finite set and a finite union of Hölder continuous curves.     

Scheduling start time dependent jobs to minimize the total weighted completion time

This paper deals with a single machine scheduling problem with start time dependent job processing times. The job processing times are characterized by decreasing linear functions dependent on their start times. The problem is to find a schedule for which the total weighted completion time is minimized. It is proved that the problem is NP-hard. Some properties of special cases of the general problem are also given. Based on these results, two heuristic algorithms are constructed and their performance is compared.     

An exact method for minimizing the total treatment time in intensity-modulated radiotherapy

In this paper, we solve a combinatorial optimization problem that arises from the treatment planning of a type of radiotherapy where intensity is modulated by multileaf collimators (MLC) in a step-and-shoot manner. In Ernst et al [INFORMS Journal on Computing 21 (4) (2009): 562–574], we proposed an exact method for minimizing the number of MLC apertures needed for a treatment. Our method outperformed the fastest algorithms available at the time. We refer to our method as the CPI method. We now attempt to minimize the total treatment time by modifying our CPI method. This modification involves non-trivial work, as some of the search space elimination schemes used in the CPI method cannot be applied in here. In our numerical experiments, we again compare our new method with the fastest algorithms currently available. There has been significant recent research in this area; hence we compare our method with those published in Wake et al [Computers and Operations Research 36 (2009): 795–810], Ta?kin et al [Operations Research 58 (3) (2010): 674–690] and Cambazard et al [CPAIRO (2010): 1–16]. The numerical comparisons indicate that our method generally outperformed the first two, while being competitive with the third.     

On minimizing resource consumption with constraints on the makespan and the total completion time

We investigate a single machine scheduling problem where the resource consumed depends on the release times of jobs. The objective is to minimize the total consumption subject to a constraint on the makespan or the total completion time. Results by Li are extended to the case where the consumption function is convex decreasing. A further extension to multiple consumption functions is shown. Conditions for feasibility are developed in each case.     

An outer approximation method for minimizing the product of several convex functions on a convex set

This paper addresses the minimization of the product ofp convex functions on a convex set. It is shown that this nonconvex problem can be converted to a concave minimization problem withp variables, whose objective function value is determined by solving a convex minimization problem. An outer approximation method is proposed for obtaining a global minimum of the resulting problem. Computational experiments indicate that this algorithm is reasonable efficient whenp is less than 4.This research was partly supported by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. (C)03832018 and (C)04832010.     

Single-machine scheduling of multi-operation jobs without missing operations to minimize the total completion time

We consider the problem of scheduling multi-operation jobs on a singe machine to minimize the total completion time. Each job consists of several operations that belong to different families. In a schedule each family of job operations may be processed as batches with each batch incurring a set-up time. A job is completed when all of its operations have been processed. We first show that the problem is strongly NP-hard even when the set-up times are common and each operation is not missing. When the operations have identical processing times and either the maximum set-up time is sufficiently small or the minimum set-up time is sufficiently large, the problem can be solved in polynomial time. We then consider the problem under the job-batch restriction in which the operations of each batch is partitioned into operation batches according to a partition of the jobs. We show that this case of the problem can be solved in polynomial time under a certain condition.