| 1. |
- Bidot, Julien, et al.
(författare)
-
A theoretic and practical framework for scheduling in a stochastic environment
- 2009
-
Ingår i: Journal of Scheduling. - : Springer Science and Business Media LLC. - 1094-6136 .- 1099-1425. ; 12:3, s. 315-344
-
Tidskriftsartikel (refereegranskat)abstract
- There are many systems and techniques that address stochastic planning and scheduling problems, based on distinct and sometimes opposite approaches, especially in terms of how generation and execution of the plan, or the schedule, are combined, and if and when knowledge about the uncertainties is taken into account. In many real-life problems, it appears that many of these approaches are needed and should be combined, which to our knowledge has never been done. In this paper, we propose a typology that distinguishes between proactive, progressive, and revision approaches. Then, focusing on scheduling and schedule execution, a theoretic model integrating those three approaches is defined. This model serves as a general template to implement a system that will fit specific application needs: we introduce and discuss our experimental prototypes which validate our model in part, and suggest how this framework could be extended to more general planning systems.
|
|
| 2. |
- Brauner, Nadia, et al.
(författare)
-
Lawler’s minmax cost algorithm: optimality conditions and uncertainty
- 2015
-
Ingår i: Journal of Scheduling. - : Springer Science and Business Media LLC. - 1094-6136 .- 1099-1425.
-
Tidskriftsartikel (refereegranskat)abstract
- The well-known O(n^2) minmax cost algorithm of Lawler (MANAGE SCI 19(5):544–546, 1973) was developed to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We propose two results related to Lawler’s algorithm. Lawler’s algorithm delivers one specific optimal schedule while there can exist other optimal schedules. We present necessary and sufficient conditions for the optimality of a schedule for the problem with strictly increasing cost functions. The second result concerns the same scheduling problem under uncertainty. The cost function for each job is of a special decomposable form and depends on the job completion time and on an additional numerical parameter, for which only an interval of possible values is known. For this problem we derive an O(n^2) algorithm for constructing a schedule that minimizes the maximum regret criterion . To obtain this schedule, we use Lawler’s algorithm as a part of our technique.
|
|
| 3. |
- Carlsson, Mats, et al.
(författare)
-
Exact and metaheuristic methods for a real-world examination timetabling problem
- 2023
-
Ingår i: Journal of Scheduling. - 1094-6136 .- 1099-1425. ; 26, s. 353-
-
Tidskriftsartikel (refereegranskat)abstract
- We propose a portfolio of exact and metaheuristic methods for the rich examination timetabling problem introduced by Battistutta et al. (in: Hebrard, Musliu (eds) 17th International conference on the integration of constraint programming, artificial intelligence, and operations research (CPAIOR-2020), LNCS, vol 12296. Springer, Berlin, pp 69–81, 2020). The problem includes several real-world features that arise in Italian universities, such as examinations split into two parts, possible requirements of multiple rooms for a single examination, and unavailabilities and preferences for periods and rooms. We developed a CP model encoded in the MiniZinc modeling language and solved it with Gecode, as well as two MIP models solved with Gurobi. The first MIP model is encoded natively and the second one again in MiniZinc. Finally, we extended the metaheuristic method based on simulated annealing of Battistutta et al. by introducing a new neighborhood relation. We compare the different techniques on the real-world instances provided by Battistutta et al., which have been slightly refined by correcting some semantic issues. Finally, we developed a solution checker that is publicly available, together with all instances and solutions, for inspection and future comparisons.
|
|
| 4. |
- Damaschke, Peter, 1963
(författare)
-
Scheduling search procedures
- 2004
-
Ingår i: Journal of Scheduling. - 1099-1425 .- 1094-6136. ; 7:5, s. 349-364
-
Tidskriftsartikel (refereegranskat)abstract
- We analyze preemptive on-line scheduling against randomized adversaries, with the goal to finish an unknown distinguished target job. Our motivation comes from clinical gene search projects, but the subject leads to general theoretical questions of independent interest, including some natural but unusual probabilistic models. We study problem versions with known and unknown processing times of jobs and target probabilities, and models where the on-line player gets some randomized extra information about the target. For some versions we get optimal competitive ratios, expressed in terms of given parameters of instances.
|
|
| 5. |
- Damaschke, Peter, 1963
(författare)
-
Scheduling search procedures: The wheel of fortune
- 2006
-
Ingår i: Journal of Scheduling. - : Springer Science and Business Media LLC. - 1099-1425 .- 1094-6136. ; 9:6, s. 545-557
-
Tidskriftsartikel (refereegranskat)abstract
- Suppose that a player can make progress on n jobs, and her goal is to complete a target job among them, as soon as possible. Unfortunately she does not know what the target job is, perhaps not even if the target exists. This is a typical situation in searching and testing. Depending on the players prior knowledge and optimization goals, this gives rise to various optimization problems in the framework of game theory and, sometimes, competitive analysis. Continuing earlier work on this topic, we study another two versions. In the first game, the player knows only the job lengths and wants to minimize the completion time. A simple strategy that we call wheel-of-fortune (WOF) is optimal for this objective. A slight and natural modification however makes this game considerably more difficult: If the player can be sure that the target is present, WOF fails. However, we can still construct in polynomial time an optimal strategy based on WOF. We also prove that the tight absolute bounds on the expected search time. In the final part, we study two competitive-ratio minimization problems where either the job lengths or the target probabilities are known. We show their equivalence, describe the structure of optimal strategies, and give a heuristic solution.
|
|
| 6. |
- de Werra, D., et al.
(författare)
-
Complexity of some special types of timetabling problems
- 2002
-
Ingår i: Journal of Scheduling. - : John Wiley & Sons. - 1094-6136 .- 1099-1425. ; 5:2, s. 171-183
-
Tidskriftsartikel (refereegranskat)abstract
- Starting from the simple class-teacher model of timetabling (where timetables correspond to edgecolorings of a bipartite multigraph), we consider an extension defined as follows: we assume that the set of classes is partitioned into groups. In addition to the teachers giving lectures to individual classes, we have a collection of teachers who give all their lectures to groups of classes. We show that when there is one such teacher giving lectures to three groups of classes, the problem is NP-complete. We also examine the case where there are at most two groups of classes and we give a polynomial procedure based on network flows to find a timetable using at most t periods.
|
|
| 7. |
- Obradovic, Gabrijela, 1994, et al.
(författare)
-
Scheduling the repair and replacement of individual components in operating systems: a bi-objective mathematical optimization model
- 2024
-
Ingår i: Journal of Scheduling. - 1099-1425 .- 1094-6136. ; 27:1, s. 87-101
-
Tidskriftsartikel (refereegranskat)abstract
- Preventive maintenance (PM) is performed so that failure is avoided while corrective maintenance is performed after a failure has occurred in order to restore the system back to an operational state. This research aims at scheduling PM activities for a multi-component system within a finite time horizon. We consider a setting with two stakeholders, being the system operator and themaintenanceworkshop, and two different contract types governing their joint activities, namely an availability contract and a turn-around time contract. Components in the systems that are to be maintained are sent to the maintenance workshop, which needs to schedule and perform all maintenance activities while at the same time satisfying the contract and not exceeding the workshop capacity. Our modelling is based on a mixed-binary linear optimization model of a PM scheduling problem with so-called interval costs over a finite and discretized time horizon.We enhance this scheduling model with the flow of individual components through the maintenance workshop, including stocks of spare components, both those components that need repair and the repaired ones. The resulting scheduling model is then utilized in the optimization of two main contracts, namely maximizing the availability of repaired (or new) components and minimizing the deviation from the contracted turn-around times for the components in the maintenance loop. Each of these objectives is combined with the objective to minimize the costs for maintenance of the operating system, leading to two bi-objective optimization problems. We analyse the two contracting forms between the stakeholders by studying and comparing the Pareto fronts resulting from different parameter settings, regarding minimum allowed stock levels and investments in repair capacity of the workshop. Our bi-objective mixed-binary linear optimization model is able to capture important properties of the results from the contracting forms as well as to show that, in our setting, an availability contract performs better than a turn-around time contract in terms of tractability.
|
|
| 8. |
- Ljungquist, Urban
(författare)
-
Going practical on the core competence concept : On Links, Levels, Time and Context
- 2013
-
Ingår i: Knowledge and Process Management. - : John Wiley. - 1092-4604 .- 1099-1441. ; 20:4, s. 223-231
-
Tidskriftsartikel (refereegranskat)abstract
- We update the original core competence notions of identification and development to fit high efficient innovation processes in dynamic environments, with aim to progress the concept's applicability for scholars and practitioners. To the core competence concept we add four dimensions previously missing: time (shared history and shared future aims), managerial hierarchy levels (corporate and SBU), innovation development modes and outcome types (radical/incremental and exploitation/exploration), and finally innovation team characteristics and support structure (homogenous/heterogeneous and formal/informal structure). We propose that existing core competencies are ideally explored by homogenous teams managed at the SBU-level, in structured context, which infers competitive imitation protection. The process starts with identification then progressed by a change in structure: going from formal to informal, which will increase core competence and company performance.
|
|
