Pub. online:1 Jan 2017Type:Research ArticleOpen Access
Journal:Informatica
Volume 28, Issue 4 (2017), pp. 583–608
Abstract
This paper presents a column generation-based modelling and solution approach for a teaching assistant workload scheduling problem that arises at academic institutions. A typical weekly workload schedule involves teaching deficiency classes, instructing problem-solving tutorial sessions, and allocating help-hours for students. For this purpose, a mixed-integer programming model that selects valid combinations of weekly schedules from the set of all feasible schedules is formulated. Due to the overwhelming number of variables in this model, an effective column generation procedure is developed. To illustrate the proof-of-concept along with modelling and algorithmic constructs, a case study related to the Department of Mathematics at Kuwait University is addressed. Computational results based on real data indicate that the generated schedules using the proposed model and solution procedure yield improved weekly workloads for teaching assistants in terms of fairness, and achieve enhanced satisfaction levels among assistants, as compared to schedules obtained using ad-hoc manual approaches.
Journal:Informatica
Volume 20, Issue 2 (2009), pp. 203–216
Abstract
One of the most known applications of Discrete Optimization is on scheduling. In contrast, one of the most known applications of Continuous Nonlinear Optimization is on the control of dynamic systems. In this paper, we combine both views, solving scheduling problems as dynamic systems, modeled as discrete-time nonlinear optimal control problems with state and control continuous variables subjected to upper and lower bounds. Complementarity constraints are used to represent scheduling decisions. One example we discuss in detail is the crude oil scheduling in ports, with numerical results presented.
Journal:Informatica
Volume 17, Issue 1 (2006), pp. 13–24
Abstract
We study single machine scheduling problems, where processing times of the jobs are exponential functions of their start times. For increasing functions, we prove strong NP-hardness of the makespan minimization problem with arbitrary job release times. For decreasing functions, maximum lateness minimization problem is proved to be strongly NP-hard and total weighted completion time minimization problem is proved to be ordinary NP-hard. Heuristic algorithms are presented and computationally tested for these problems.
Journal:Informatica
Volume 13, Issue 3 (2002), pp. 311–332
Abstract
Real life scheduling problems are solved by heuristics with parameters defined by experts, as usual. In this paper a new approach is proposed where the parameters of various heuristics and their random mixtures are optimized to reduce the average deviations from the global optimum.
In many cases the average deviation is a stochastic and multi-modal function of heuristic parameters. Thus a stochastic global optimization is needed. The Bayesian heuristic approach is developed and applied for this optimization. That is main distinctive feature of this work. The approach is illustrated by flow-shop and school scheduling examples. Two versions of school scheduling models are developed for both traditional and profiled schools. The models are tested while designing schedules for some Lithuanian schools. Quality of traditional schedules is defined by the number of teacher “windows”. Schedules of profiled schools are evaluated by user defined penalty functions. That separates clearly subjective and objective data. This is the second specific feature of the proposed approach.
The software is developed for the Internet environment and is used as a tool for research collaboration and distance graduate studies. The software is available at web-sites and can be ran by standard net browsers supporting Java language. The care is taken that interested persons could easily test the results and apply the algorithms and software for their own problems.
Journal:Informatica
Volume 7, Issue 3 (1996), pp. 311–336
Abstract
We consider a possibility of automating the analysis of a computer program realizing the objective function of an extremal problem, and of distributing the calculation of the function value into parallel processes on the basis of results of the analysis. The first problem is to recognize the constituent parts of the function. The next one is to determine their computing times. The third problem is to distribute the calculation of these parts among independent processes. A special language similar to PASCAL has been used to describe the objective function. A new scheduling algorithm, seeking to minimize the maximal finishing time of processing units, was proposed and investigated. Experiments are performed using a computer network.